warren@ihlpf.ATT.COM (Montgomery) (05/02/88)
Control flow seems to be an area that brings out the worst in people. There isn't one set of control structures that is right for every problem. If you want to look for the ultimate in gotos, look at some of the constructs that the AI folks use: Production rules, pattern directed invocation, blackboards, etc. That doesn't mean that these are bad, just that the problems they are solving lend themselves to different kinds of control flow. One of the most difficult to understand programs I ever came accross was a "gotoless" program written shortly after the original Djikstra article. It was a printer driver that consisted of a large outer loop "while (not_done)" and a loop body that consisted of deeply nested if-then-else's. At the leaves of the if-then-elses were statements that did something and generally set variables tested by the if-then-elses, possibly also setting the loop condition. The structure being implemented was actually a finite state machine, and fairly simple to understand as such, but impossible to discern from the style in which it was written. What I'd like to suggest is this: 1) Use control structures that are appropriate for your application and readily understood. For many problems, loops and conditionals are natural control structures, but some applications naturally call for finite state machines, production rules, or more exotic strucutres. 2) Use an implementation that makes that control structure explicit. Implementing a finite state machine obscurely to avoid gotos doesn't make the program more maintainable. -- Warren Montgomery ihlpf!warren
EGNILGES@pucc.Princeton.EDU (Ed Nilges) (05/03/88)
In article <4605@ihlpf.ATT.COM>, warren@ihlpf.ATT.COM (Montgomery) writes: > > 2) Use an implementation that makes that control structure > explicit. Implementing a finite state machine obscurely to > avoid gotos doesn't make the program more maintainable. > >-- > If you are not too concerned about efficiency, the best way to implement a finite state machine is as a two-dimensional table searched by old state and current symbol, yielding new state and perhaps some representation of an action to be carried out. The neat thing is that your end users can check or even specify the table, and (if your project is sufficiently complex) the table can serve as the basis for tools that draw finite-state diagrams, check test coverage, or even produce automated documentation. I used this technique for a now-bought-out switch manufacturer that needed to simulate one of their PBXs using a Cobol program, running on the customer's mainframe, in order to produce accurate usage reports and bills. The Cobol program had to be general, running on unpredictable machines. It didn't have to be fast. My predecessor had written a GOTO-ridden monstrosity that was ridden with bugs and impossible to understand. In the space of two months or so, a customer team and I collaborated on a table-based program that worked with every case that the customer could throw at it. The tables were clearly demarcated in the program data division, such that the switch engineers and I could clearly communicate about how the PBX worked. Gotos could have been used to implement the finite state auto- maton, but this would have tempted maintenance people to add gotos outside of the table interpreter. I've seen a compiler generated using syntax-driven techniques where subsequent changes have obscured the designer's intent and changed the language compiled because the maintainers did not have any access to the syntax tables; this is a similar situation. I'm not saying gotos are bad; the optimal and most maintainable method, IF you have cycles to burn, is a table interpreter. The technique was more popular when storage was expensive (Ref 1), since a dense representation could be used for the table. However, Gerald Weinberg describes an incident (Ref 2) in compu- s ting's early days when the method of table interpretation was used to increase quality and user/programmer communication. Poor mana- gers, in this writer's experience, have always hated the technique, since it seems to cut them out of the user/programmer communication loop; good managers like it, because it almost always works well. REFERENCES 1. Brooks, Frederick R., THE MYTHICAL MAN-MONTH: Essays in Software Engineering. Reading, MA, 1975: Addison-Wesley Publishing Company. Page 102. 2. Weinberg, Gerald M., THE PSYCHOLOGY OF COMPUTER PROGRAMMING. New York, NY, 1971: Van Nostrand Reinhold. Page 17.
UH2@PSUVM.BITNET (Lee Sailer) (05/04/88)
In article <4605@ihlpf.ATT.COM>, warren@ihlpf.ATT.COM (Montgomery) says: > >nested if-then-else's. At the leaves of the if-then-elses were >statements that did something and generally set variables tested by >the if-then-elses, possibly also setting the loop condition. The >structure being implemented was actually a finite state machine, and >fairly simple to understand as such, but impossible to discern from >the style in which it was written. This is where "literate programming" should come in. Perhaps if the author had written a long comment that said something like, "I've implemented a fsm using deeply nested if-then-elses. At the end of each if-then-else is a block of statements that do stuff, and set the state variables for the next go around. I could have uses case stements but didn't because. etc etc etc," then it wouldn't have been necessary for you to "discern" the fsm from the structure of the code. Now, this also presumes a certain degree of expertise on the part of the reade, who has to know what a fsm is, and how to program one. lee
daveb@geac.UUCP (David Collier-Brown) (05/05/88)
In article <5110@pucc.Princeton.EDU> EGNILGES@pucc.Princeton.EDU writes: | If you are not too concerned about efficiency, the best | way to implement a finite state machine is as a two-dimensional | table searched by old state and current symbol, yielding new | state and perhaps some representation of an action to be carried | out. The neat thing is that your end users can check or even | specify the table, and (if your project is sufficiently complex) | the table can serve as the basis for tools that draw finite-state | diagrams, check test coverage, or even produce automated documentation. Yup! try using Wart, from the kermit distribution. It is a full-fleged (if trivially inefficent) DFA compiler ,with a very nice notation: <state1,state2> event { some code } <state> event { more code } event { general-case code } --dave (I have a slightly more compact version, wart2) c-b -- David Collier-Brown. {mnetor yunexus utgpu}!geac!daveb Geac Computers International Inc., | Computer Science loses its 350 Steelcase Road,Markham, Ontario, | memory (if not its mind) CANADA, L3R 1B3 (416) 475-0525 x3279 | every 6 months.
david@daisy.UUCP (David Schachter) (05/07/88)
One fellow I know documented a particularly complex and obscure code with the comment "This procudure implements the <something or other> algorithm given on page <xyz> of <some book> by <some author>". (The angle bracketed items are mine.) Real helpful. If I want to understand his code, I have to get the book from a speciality bookstore or get my company to purchase library access at Stanford University. Then, hoping the edition I get is the same as his (so the page numbers match), I read some author's description of the algorithm and hope the programmer implemented the algorithm exactly. Great, just great. It is folks like him who justify, in my mind, the existence of nuclear weapons. -- David Schachter Disclaimer: My company disclaims me; being a gentleman, I return the favor.
UH2@PSUVM.BITNET (Lee Sailer) (05/07/88)
In article <1122@daisy.UUCP>, david@daisy.UUCP (David Schachter) says: > >One fellow I know documented a particularly complex and obscure code with the >comment "This procudure implements the <something or other> algorithm given >on page <xyz> of <some book> by <some author>". (The angle bracketed items >are mine.) > >Real helpful. If I want to understand his code, I have to get the book from >a speciality bookstore or get my company to purchase library access at Stanford Tastes differ, and gentlefolk can disagree. I am usually delighted when this type of comment appears in the code. The book nearly always makes much better reading than some guys half-literate comments. Real Soon Now, we'll all be using Xanadu, and the comments in the code will actually point at the reference on a disk somewhere, and you'll be able to access it online. 8-) lee
shebs%defun.utah.edu.uucp@utah-cs.UUCP (Stanley T. Shebs) (05/07/88)
In article <1122@daisy.UUCP> david@daisy.UUCP (David Schachter) writes: >One fellow I know documented a particularly complex and obscure code with the >comment "This procudure implements the <something or other> algorithm given >on page <xyz> of <some book> by <some author>". (The angle bracketed items >are mine.) Sounds perfectly fine to me. Why waste all kinds of space repeating other people's words? Or worse, not mentioning at all that the algorithm derives from somewhere else? In all fairness, the bald citation is insufficient - there should also be one or two lines like "the algorithm is based on the use of multi-colored pointers cycling around in something resembling a butterfly FFT". This will jog the memory of the informed reader, and strongly suggest to the ignorant reader that there are a lot of prerequisites to understanding this code. stan shebs shebs@cs.utah.edu
daveb@geac.UUCP (David Collier-Brown) (05/09/88)
In article <1122@daisy.UUCP> david@daisy.UUCP (David Schachter) writes: | One fellow I know documented a particularly complex and obscure code with the | comment "This procudure implements the <something or other> algorithm given | on page <xyz> of <some book> by <some author>". (The angle bracketed items | are mine.) | Real helpful. If I want to understand his code, I have to get the book from | a speciality bookstore or get my company to purchase library access at Stanford | University. Then, hoping the edition I get is the same as his (so the page | numbers match), I read some author's description of the algorithm and hope | the programmer implemented the algorithm exactly. Great, just great. That was probably me. You'll find the photocopies of the pages in the book in the file with the master man pages and design notes for the program. | It is folks like him who justify, in my mind, the existence of nuclear weapons. That's odd, I don't **remember** working for a nuclear weapons company... --dave ((;-)) c-b -- David Collier-Brown. {mnetor yunexus utgpu}!geac!daveb Geac Computers International Inc., | Computer Science loses its 350 Steelcase Road,Markham, Ontario, | memory (if not its mind) CANADA, L3R 1B3 (416) 475-0525 x3279 | every 6 months.
jtkrist@ihlpf.ATT.COM (05/09/88)
In article <1122@daisy.UUCP> david@daisy.UUCP (David Schachter) writes: >One fellow I know documented a particularly complex and obscure code with the >comment "This procudure implements the <something or other> algorithm given >on page <xyz> of <some book> by <some author>". (The angle bracketed items >are mine.) > golly, this could be me! whenever i need to implement an algorith, i look first in knuth and if i find what i need, i transliterate the algorithm, as closely as possible, in the language i'm using - yes i know it's not structured and there are lots of labels and gotos, but it works - who was it who said that scientists stand on each other's shoulders, while programmers stand on each other's toes? > >It is folks like him who justify, in my mind, the existence of nuclear weapons. > > -- David Schachter if the state of illinois disappears tonight, you know what happened - maybe i can talk jim thompson (our governor for life) into a software defense initiative? -- James T. Krist AT&T Bell Laboratories IHP-1F230 Naperville, IL 60566 ...!ihnp4!ihlpf!jtkrist (312)-416-5099