Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Channels ▼



Algebraic Specification is the Answer

Dear DDJ,

In Michael Swaine's recent column about object-oriented programming on SD '88 ("Programming Paradigms," June issue) there was a question: Are there any rules to decide what objects to define? I think--in contrast to the panelists--there is a good way to construct programs with well-chosen objects. Of course, if you start from scratch nothing will be changed for the better.

My answer is simply to use algebraic specification to define the problem and its solution. That means use a specific style of functional programming with precise semantics. You have to define entities by functions and conditional equations to enhance and combine the specifications to describe the problem at hand. This way you will easily get a well-structured problem solution, telling what is to be done.

And now consider object-oriented programming as the way to tell how the solution is to be realized on the computer. You will find a direct correspondence between specification modules and objects needed in the implementation. I can't speak here about all the other--and more essential--merits of this approach because there is not enough room. But I think we should favor the use of formal methods already in the design phase to overcome such questions as the one mentioned above--and a lot of other difficulties in programming.

Dr. Lutz Pietschker

Muhldorf, West Germany

Source Code Correction

Dear DDJ,

I like Kent Porter's "sub"stitute for the DOS dir command very much ("Structured Programming," August issue). You may be interested in a minor error in the source code: in function SizeInK, "IF size MOD Blocksize < >0" should be "IF files.size MOD Blocksize < > 0." I stumbled on this when I used "sub" on a TEX pixel directory which happened to contain files with exactly 4,096 bytes.

William F. Trench

Trinity University

San Antonio, Texas

Reader Offers Split Screen Action Diagram Editor

Dear DDJ,

It was interesting to read Martin Stitt's article on action diagrams--or action charts as he calls them ("Using Action Charts," September issue). These diagrams have been around for some time, competing against other diagramming methods for attention. I find action diagrams rather useful for defining mini specs in data flow diagrams. They are clear, concise, and much more accepted by the user community and the programming staff than structured English.

However, typing all those macros to create such a diagram is tedious and diminishes its effectiveness. I have created a split screen action diagram editor which relieves analysts of having to worry about the constructs, and instead, they can concentrate on showing the logic flow. I urge readers to contact me for a free copy at 6087 Dana Dr., Norcross, GA 30093; 404-925-3122.

Sam Johnson

Norcross, Ga.

Real Programmers Don't Use Assembly Language

Dear DDJ,

I really appreciated Ratcliffs and Metzener's article on Pattern Matching ("Pattern Matching by Gestalt," July issue). It was excellent! I was also quite intrigued with the algorithm itself, but like all real programmers, I dislike having to use assembly language.

I certainly don't believe that assembly language is necessary in this case. I therefore implemented it in C using a recursive function. Anyone interested can have it (Listing Two).

The execution times of the code on a 6-MHz AT in SCO Xenix C were about twice that of what were reported in the article on an 8-MHz machine. I believe the trade-off of time for readability is quite worthwhile.

Thanks again for a great article.

Joe Preston

Agent Systems Inc.

Dallas, Texas

Dear DDJ,

I really enjoyed Ratcliff's and Metzner's article "Pattern Matching by Gestalt" in the July issue. For your readers who use computers that are not IBM PC compatible, I have rewritten the simil and compare routines in C (Listing One). I have left the variable names and program structure very close to the assembler version to make it easy to follow.

Rick Orsborn

Wheat Ridge, Colo.

Debuggers' Debilities

Dear DDJ,

The review of the current state of C compilers in the August issue was very interesting. ("Speed Trials: Five Cs Compared.") I was especially pleased to see that you tested code generation and its correctness. This gives a better feeling for the quality of the compiler than using only the benchmark timings.

However, I was puzzled by the emphasis on debuggers. There were no details on what made one debugger stand above the others, but it's something of a moot point anyway. Software debuggers are not the best tool for the job and should not influence the rating of a compiler.

Specifically, every software debugger I've seen is weak in three places. I've use Microsoft's Codeview, so I'll use it to illustrate my points, but the same criticisms apply to other debuggers too.

    1. Transparency. Adding the debugger to the system should not change the behavior of the application program. Software debuggers almost all fail here because they load below the program in RAM. A program that passes data on the stack (like C, for example,) may act differently when loaded at the higher location. Beside that, the RAM used by the debugger is that much less heap available to the program. Codeview is particularly bad here--not many serious programs won't notice the loss of 200K.

    2. Independence. The performance of the debugger should require as little as possible of the other parts of the system. At a minimum, it should not expect the program to leave the interrupt vector table alone. Good ones shouldn't depend on DOS, either. Codeview fails here, too. Trash the keyboard interrupt vector, and down it goes.

    3. Reliability. The debugger should be able to protect itself from the application. C programs are famous for crashing when people use uninitialized pointers and romp through memory that doesn't belong to them. Some software debuggers claim to use the capabilities of the 80386 to protect themselves. Some may work. The one I tried didn't.

The only thing I've found that meets these requirements is a hardware-based debugger. I use Periscope, but there are others out there too. Periscope uses 64K of memory on an expansion board to store its code and data. The memory can be installed in memory space, which is unavailable to the program in the first place, so you lose no bytes for your application. The memory is write-protected so your application can't trash it, too. Furthermore, Periscope reloads the interrupt vectors it needs for I/O while it is active, so your programs can even trash them and not crash the debugger. Their real trump, though, is the hardware trace circuitry on the board. You can run at full speed, quietly monitoring the running application; then break out to the debugger when a programmable break condition occurs; and then examine the hardware traceback buffer to see exactly what your program was doing before and after the break condition occurred. Periscope even has source-level debugging if that's what you want. I've used it to debug a 500K application which loads under DOS then deletes DOS and disk BIOS from the system entirely while it's running to use the extra heap. Try that with Codeview!

In short, software debuggers fall far short of what is attainable with hardware based products. This being the case, it's not fair to rate these top line compilers on the basis of the accompanying debuggers. Anyone who's serious about debugging (meaning their job is on the line) probably won't use them anyway. The protection capabilities of the 80386 open the way for software products that make the grade, but they aren't here yet, and you can bet they won't be freebies when they come.

Jim Castleberry

Orlando, Fla.



<a name="01e6_0008">

#include <string.h>

int stcknum;
char *ststr1l[26];
char *ststr2l[26];
char *ststr1r[26];
char *ststr2r[26];

int simil (str1, str2)    /*`Pattern Matching by Gestalt' */
char *str1, *str2;        /*by John W. Ratcliff           */
                          /*Dr. Dobb's Journal #141.      */
{                         /*July 1988                     */
    int len1;
    int len2;
    int ncmp;
    int score;
    char *di;
    char *si;
    char *de;
    char *se;
    char *cl1
    char *cl2;
    char *cr1;
    char *cr2;

    score = 0;
    stcknum = 0;

    len1 = strlen(str1);
    len2 = strlen(str2);
    if (len1 == 0 || len2 == 0)
       return (score);

    pushst (str1, str1+len1-1, str2, str2+len2-1);

    while (stcknum != 0)
        popst (&si, &se, &di, &de);
        cl1 = si;
        cl2 = di;
        cr1 = se;
        cr2 = de;
        if ((ncmp=compare (&si, &se, &di, &de)) !=0)
            score += ncmp*2;
            if (cl1 != si    && cl2 != di   &&
               (cl1 != si-1  || c12 != di-1))
               pushst (cl1, si-1, cl2, di-1);
            if (se    != cr1 && de    != cr2 &&
               (se+1  != cr1 || de+1  != cr2))
               pushst   (se+1, cr1, de+1, cr2);
     return  (100*score/(len1+len2));

int compare (si, se, di, de)
char **si;
char **se;
char **di;
char **de;
  int maxchars;
  int l;
  int len1;
  char *i;
  char *j;
  char *m;
  char *n;
  char *s2end;
  char *cl1;
  char *cl2;
  char *cr1;
  char *cr2;

  maxchars = 0
  for (i=(*si); i <= *se-maxchars; i++)
      len1 + *se - i;
      for (j=(*di); j <= *de-maxchars; j++)
         s2end = j + len1;
         if (s2end > *de)
             s2end = *de;
         for (m=i,n=j,l=0;  *m==*n && n <=s2end; m++,n++)
         if (1 > 0)
            if (l <= maxchars)
                j += l-1;
                cl1 = i;
                cl2 = j;
                maxchars = 1;
                j += l;
                cr2 = j;
                cr1 = i+l;
  *si = cl1;
  *se = cr1;
  *di = cl2;
  *de = cr2;
  return (maxchars);

pushst (si, se, di, de)
char *si;
char *se;
char *di;
char *de;
   ststr1l[stcknum] = si;
   ststr1r[stcknum] = se;
   ststr2l[stcknum] = di;
   ststr2r[stcknum] = de;

popst (si, se, di, de)
char **si;
char **se;
char **di;
char **de;
    *si = ststr1l[stcknum];
    *se = ststr1r[stcknum];
    *di = ststr2l[stcknum];
    *de = ststr2r[stcknum];

<a name="01e6_0009"><a name="01e6_0009">
<a name="01e6_000a">
<a name="01e6_000a">

int simil (s1, s2)
/* Ratcliff/Obershelp Pattern Matching */
char *1, *2;
  short l1, l2;

  l1 = strlen(s1);
  l2 = strlen(s2);

  if (l1 == 1)                 /* check for the easiest case */
    if (l2 == 1)
      if (*s1 == *s2)

  return(200 * GCsubstr(s1, s1 + l1, s2, s2 + l2) / (l1 + l2));

int GCsubstr(st1, end1, st2, end2)
/* recursive greatest common sub-string */
char *st1, *end1, *st2, *end2;
  register char *a1, *b1, *s1, *a2, *b2, *s2;
  short max, i;

  if (end1 <= st1)              /* s1 empty */
    return (0);
  if (end2 <= st2)              /* s2 empty */
    return (0);
  if (end1 == st1 + 1)          /* s1 has one char, */
    if (end2 == st2 + 1)        /* and s2 has one char. */
      return(0);                /* They cannot be equal. */

  max = 0;
  b1 = end1; b2 = end2;

  for (a1 = st1; a1 < b1; a1++)
    for (a2 = st2; a2 < b2; a2++)
      if (*a1 == *a2)
        {               /* How long is the common sub-string? */
        for (i = 1; a1[i] && (a1[i] == a2[i]); i++)
        if (i > max)
          max = i; s1 = a1; s2 = a2;
          b1 = end1 - max; b2 = end2 - max;
  if (! max)
    return (0);

  max += GCsubstr(s1 + max, end1, s2 + max, end2);        /* RHS */
  max += GCsubstr(st1, s1, st2, s2);                      /* LHS */


Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.