'Software Tools in Turbo Pascal' Blog RSS Feed

Goto, goto ..

Actor — Wed, 03 Dec 2008 12:16:45 -0700

"...go to, go to."
William Shakespeare, Hamlet, Act I, Scene 3, Line 112.

Although I would be he first to proclaim that the goto should be eschewed, I am not a purist who advocates its avoidance at all costs. In his paper "Goto Statement Considered Harmful", E.W. Dijkstra pointed out that the overuse of goto was detrimental to readability of code but did not advocate its abolition. Of course, given that you simply can't program in Fortran without using goto, advocating the total avoidance of goto at a time when Fortran was the most popular language going would be unrealistic. There is no way of knowing his views today. Whatever! The point is that code should be readable. There are times, albeit rarely, when the use of goto actually contributes to readability.

Case in point: in chapter 5 of Software Tools in Pascal, Kernighan and Plauger state, "There are ... some complications because Pascal doesn't have a return statement to permit an early exit from a function. Most of the complication ... comes from circumventing that omission." goto would have solved this problem but K&P refused to use it.

Of course Turbo Pascal and other implementations based on the ANSI standard provide the exit statement for early exit from a function, but that's not the point. My point is even when return or exit are available there are times when goto is an acceptable choice. For example I would have no problem with the following use of goto and would not mark down a student's work for using it:

    {
        find position of white king
    }
    for i := 'a' to 'h' do
        for j := 1 to 8 do
            if Piece[i,j] = WHITEKING then
                goto Found ;
    {
        if we get to this point then ..
    }
    WriteLn ('Can''t happen.  White king is not on the board.') ;
    Halt ;

Found:
    { code continues here }

Note that break will not do here, first, because we have a nested loop to jump out of, and second, because break would not bypass the error message. To avoid goto we have to resort to a flag.

    {
        find position of white king
    }
    for i := 'a' to 'h' do begin
        for j := 1 to 8 do begin
            Found := (Piece[i,j] = WHITEKING) ;
            if Found then
                break { jump out of inner loop }
        end ;
        if Found then
            break { jump out of outer loop }
    end ;
    {
        if we get to this point then ..
    }
    if NOT Found then begin { error message }
        WriteLn ('Can''t happen.  White king is not on the board.') ;
        Halt
    end ;
    { code continues here }

I submit that the first example is much more readable than the second. Even with break available it provides cleaner code. The second has three comparisons to the first's single comparison.

Now I must admit that this example is somewhat contrived. Given this problem I would put the search in a separate procedure:

Procedure FindKing (Var Col : Char ; Var Row : Byte) ;

Var
    i : Char ;
    j : Byte ;

begin
    {
        find position of white king
    }
    for i := 'a' to 'h' do
        for j := 1 to 8 do
            if Piece[i,j] = WHITEKING then begin
                Col := i ;
                Row := j ;
                Exit
            end ;
    {
        if we get to this point then ..
    }
    WriteLn ('Can''t happen.  White king is not on the board.') ;
    Halt
end ;

However, my choice of writing a search procedure is made in the interest of program modularity, not to avoid goto. Happily Exit, break and Halt are all available, but if they were not then goto is still my choice, even in the procedure.

File encryption and decryption, Part II

Actor — Sun, 10 Feb 2008 00:33:12 -0700

One more post on encryption before moving on to other things.

In Part I, I submitted an encryption program that "should prevent the casual snoop from decoding your files." The program's security can be increased tremendously by using the random number generator to generate the key. As it stands the key must be typed in on the command line, a feature that encourages the use of short keys. When the program gets to the end of the key it goes back to the key's beginning and reuses it. In our example we used "buttermilk" as the key. In a file of 500 characters a codebreaker would then get 50 clues to the key.

The random number generator will produce sequences of tens of thousands of characters before it begins to repeat itself. The first problem we have to solve is how to get the random number generator to generate the same sequence during decoding. We solve this by giving the program a "pin" of four characters. Since each number is 8 bits we have a 32 bit seed or 4,294,967,296 possible keys. Of course the user is most likely to use pins made up of alphanumeric characters so there are more like 15,000,000 most probable keys. A user who limits himself to keys made up of easily remembered words limits himself even further. Nevertheless, the number of most probable keys is still in the 100s of thousands.

Program Crypt ;
{
    Crypt -- encrypt and decrypt
}
var
    Pin      :  String ;
    Ch       :  Char ;

begin
   if ParamCount > 0 then
      begin
         Pin := Copy (ParamStr(1), 1, 4) ;
         if Length(Pin) >= 4 then begin
            RandSeed := Ord(Pin[4])
                     + 256*Ord(Pin[3])
                     + 256*256*Ord(Pin[2])
                     + 256*256*256*Ord(Pin[1]) ;
            while NOT eof do begin
               Read(Ch) ;
               Write (Chr(Ord(Ch) XOR (Random(128) + 128)))
            end
         end
         else
             WriteLn('Pin number must be at least four characters long.')
      end
   else
      WriteLn('usage: crypt key')
end.

A few more comments are in order before we leave this subject behind.

First, users of this algorithm are usually advised that their data can be made more secure by encoding it multiple times, i.e., encode the data first with one key, then encode it again using a second key (maybe even three or four times, each time with a different key). Unfortunately the EOF bug we encountered in the first version will return full force under multiple encodings so we must limit ourselves to a single encryption.

Second, the method of encrypting a file would use redirection, i.e,

     crypt Act! < clear.txt > coded.txt

which leaves the file clear.txt on the computer. It will have to be deleted. Unfortunately, as most users of DOS know, deleting the file does not completely remove it from the disk, it only marks the space it occupied as available. Anyone hacking your machine would probably concentrate of undeleting the file rather than decoding its child. The file would need to be wiped clean from the machine, not merely deleted. How you could do this is beyond what we are trying to do here.

If your machine is physically secure you don't have to delete the original or even encrypt it. The program is most effective in moving a file from one machine to another, either on a disk carried by a trusted courier or through cyberspace.

Finally, I must state (even though it should be obvious) that it is imperative that a different pin be used for each file encoded (or re-encoded).

Bit-manipulation

Actor — Sun, 27 Jan 2008 18:39:33 -0700

In his infamous rant Why Pascal Is Not My Favorite Programming Language Brian Kernighan says
"There is a paucity of operators ... In particular, there are no bit-manipulation operators (AND, OR, XOR, etc.). I simply gave up trying to write the following trivial encryption program in Pascal:

     i := 1;
     while getc(c) <> ENDFILE do begin
             putc(xor(c, key[i]));
             i := i mod keylen + 1
     end

because I couldn't write a sensible 'xor' function."

The amazing part of this statement is that I cannot fathom why he found it so hard to write an xor function. It's simply not that hard. In this post we take up the challenge.

We will assume that Kernighan's compiler did not have the type Byte and this may one source of his problem. However, Byte is simply a subrange of the integers (0 .. 255) so this is easily surmounted. We can also safely assume that he had access to the Boolean operators NOT, OR and AND.

Our project is to write four functions:

          BitNot (n : Byte) : Byte ;
          BitOr (m,n : Byte) : Byte ;
          BitAnd (m,n : Byte) : Byte ;
          BitXor (m.n : Byte) : Byte ;

Our strategy is to create a type

          Type
              BitWiseType = Array [0 .. 7] of Boolean ;

and then copy (and convert) each bit into variables of type BitWiseType where they can easily be handled by the Boolean operators. The conversion from Byte to BitWiseType is a simple adaptation of the mathematician's standard algorithm for converting from decimal to binary: repeatedly divide the number by two until the quotient is zero, taking the remainder as the next binary digit. To go from BitWiseType to Byte we start with a radix of 1, multiply by the least significant bit, then double the radix, go to the next bit and repeat for all bits.

Of course a XOR b is the same as (a AND (NOT b)) OR ((NOT a) AND b) so the final function BitXor can be defined in terms of the previous ones.

Of course Turbo Pascal has NOT, OR, AND and XOR which can be used as either strictly Boolean operators or as bitwise operators. Which definition is intended is determined by context which Pascal's strong typing facilitates. This program is unusual in that there are a finite number of possible inputs, 65536 to be exact, so we can exhaustively test our work. This test phase is the only part of our program where we will the the Turbo Pacal XOR.

  1 Program BitWise ;
  2 {
  3    implements bitwise functions for compilers that do not have them
  4 }
  5    Type
  6       BitWiseType = Array [0 .. 7] of Boolean ;
  7 
  8    Procedure GetBits (Var m : BitWiseType ; n : Byte) ;
  9    {
 10       copies a byte into an array of Boolean
 11    }
 12    Var
 13       i  :  0 .. 7 ;
 14 
 15    begin
 16       for i := 0 to 7 do begin
 17          m[i] := (n MOD 2 = 1) ;
 18          n    := n DIV 2
 19       end
 20    end ;
 21    
 22    Procedure PutBits (m : BitWiseType ; Var n : Byte) ;
 23    {
 24       copies an array of Boolean into a byte 
 25    }
 26    Var
 27       i     :  0 .. 7 ;
 28       Radix :  Byte ;
 29 
 30    begin
 31       radix := 1 ;
 32       n     := 0 ;
 33       for i := 0 to 7 do begin
 34          n := n + radix*Ord(m[i]) ;
 35          Radix := 2*Radix
 36       end
 37    end ;
 38 
 39    Function BitNot (n : Byte) : Byte ;
 40    {
 41       bitwise not
 42    }
 43    Var
 44       i  :  0 .. 7 ;
 45       a  :  BitWiseType ;
 46 
 47    begin
 48       GetBits(a, n) ;
 49       for i := 0 to 7 do
 50          a[i] := NOT a[i] ;
 51       PutBits(a, n) ;
 52       BitNot := n
 53    end ;
 54 
 55    Function BitOr (m,n : Byte) : Byte ;
 56    {
 57       bitwise or
 58    }
 59    Var
 60       i     :  0 .. 7 ;
 61       a,b,c :  BitWiseType ;
 62 
 63    begin
 64       GetBits(a, m) ;
 65       GetBits(b, n) ;
 66 
 67       for i := 0 to 7 do
 68          c[i] := a[i] OR b[i] ;
 69 
 70       PutBits(c, n) ;
 71 
 72       BitOr := n
 73    end ;
 74    
 75    Function BitAnd (m,n : Byte) : Byte ;
 76    {
 77       bitwise and
 78    }
 79    Var
 80       i     :  0 .. 7 ;
 81       a,b,c :  BitWiseType ;
 82 
 83    begin
 84       GetBits(a, m) ;
 85       GetBits(b, n) ;
 86 
 87       for i := 0 to 7 do
 88          c[i] := a[i] AND b[i] ;
 89 
 90       PutBits(c, n) ;
 91 
 92       BitAnd := n
 93    end ;
 94 
 95    Function BitXor (m,n : Byte) : Byte ;
 96    {
 97       bitwise xor
 98    }
 99    begin
100       BitXor := BitOR (BitAnd(m, BitNot(n)), BitAnd(BitNot(m), n))
101    end ;
102 
103 Var
104    m,n,
105    i,j   :  Byte ;
106 
107 begin
108    for m := 0 to 255 do 
109       for n := 0 to 255 do begin
110          i := BitXor (m,n) ;
111          j := m XOR n ;
112          WriteLn (m:5, n:5, i:10, j:5, i - j:10)
113       end
114 end.

File encryption and decryption, Part I

Actor — Sat, 19 Jan 2008 17:42:35 -0700

The next program is one which appeared in the original Software Tools but not in Software Tools in Pascal. The program is Crypt which encrypts and decrypts a text file.

The algorithm for the encryption is what cryptologists call a "one time pad" (google it). When properly used it is theoretically unbreakable. What we are doing here does not include all the steps entailed in properly using the algorithm but it should prevent the casual snoop from decoding your files.

The algorithm consists of merging the input stream of data with a second stream, the key, to produce an output stream of encrypted data. We extract the ascii codes from each char of input and from each char of the key. A bitwise XOR operation gives us the ascii code for the output which is converted back to a char. Here is the code for Crypt.

Program Crypt ;
{
	Crypt -- encrypt and decrypt
}
var
	Key      :  String ;
	KeyLen   :  Byte ;
	i        :  Byte ;
	Ch       :  Char ;

begin
	if ParamCount > 0 then
		begin
			Key      := ParamStr(1) ;
			KeyLen   := Length(Key) ;

			i := 1 ;
			while NOT eof do begin
				Read(Ch) ;
				Write (Chr(Ord(Ch) XOR Ord(Key[i]))) ;
				i := (i MOD KeyLen) + 1
			end
		end
	else
		WriteLn('usage: crypt key')
end.

The key is a string up to 255 characters long. The input and output files are selected by redirection. E.g.:

crypt keystring < in.txt > out.txt

The elegant property of the XOR operator is that it is its own reciprocal operator. I.e., if

	c = a XOR b

then

	b = a XOR c

This allows us to use the same program for both encryption and decryption by merely switching the source and destination files.

OK! Try the following:

crypt buttermilk > crypt.dat
Now is the time for all good men to come to the aid of their country.
^Z

This should encrypt "Now is the time for all good men to come to the aid of their country." and store it in the file crypt.dat. Now we should be able to get the original text back by using crypt again. However, if we redirect crypt.dat back though crypt we get

	crypt buttermilk < crypt.dat
	N

All we get is the leading N. Why? Clearly there is a bug in the program.

The bug lies in the fact that for text files DOS treats Chr(26) as an end-of-file marker. When the 'u' in 'buttermilk' meets the 'o' in 'Now is the time...' we get

	Chr(Ord('o') XOR Ord('u')) = Chr(26)

In encrypting any file with any key we can expect this condition to surface frequently.

One easy fix for this is to assume that the input will consist only of the standard ascii characters, Chr(0) .. Chr(127). In this case the most significant bit will always be zero. If we make sure that the first bit of the key is one then the resulting encrypted bit will be one. Here is the modified code.

Program Crypt ;
{
	Crypt -- encrypt and decrypt
}
		Function Map (S : String) : String ;
		{
			maps ascii characters onto the extended ascii set         
		}
		Var
			i  :  Byte ;
		
		begin
			for i := 1 to Length(S) do
				if Ord(S[i]) < 128 then
					S[i] := Chr(Ord(S[i]) + 128) ;
			Map := S
		end ;


var
	Key      :  String ;
	KeyLen   :  Byte ;
	i        :  Byte ;
	Ch       :  Char ;

begin
	if ParamCount > 0 then
		begin
			Key      := Map(ParamStr(1)) ;
			KeyLen   := Length(Key) ;

			i := 1 ;
			while NOT eof do begin
				Read(Ch) ;
				Write (Chr(Ord(Ch) XOR Ord(Key[i]))) ;
				i := (i MOD KeyLen) + 1
			end
		end
	else
		WriteLn('usage: crypt key')
end.

Now all the encrypted code is mapped to the extended ascii set. We can still use the same program for both encryption and decryption.

The bug survives but in a more tolerable form. An uncrypted file that contains an extended ascii character could still generate an unexpecgted eof. I doubt that a totally satisfactory solution can be found. For now we'll simply list it as a "known bug."

Command line parameters

Actor — Sun, 13 Jan 2008 13:39:26 -0700

The Turbo Pascal functions ParamStr and ParamCount give us access to command line arguments. ParamCount returns the number of command line arguments while ParamStr(i : Word) returns the individual parameter strings. Ekho illustrates the use of these two functions. We use the spelling Ekho instead of Echo to avoid colliding with the DOS command ECHO.

Program Ekho ;
{
   echo command line arguments to output.
}
Uses
   Tools ;

Var
   i  :  Byte ;

begin
   for i := 0 to ParamCount do
      Write (ParamStr(i), BLANK) ;
   WriteLn
end.

Note that even if no parameters are included on the command line we still get output. ParamStr(0) is the executable file itself. Thus:

c:\pascal\tools\ekho
C:\PASCAL\TOOLS\EKHO.EXE

The next few programs we write will use command line parameters.

Trimming strings

Actor — Wed, 02 Jan 2008 02:43:07 -0700

Here, for completeness without further comment, is the code for RTrim, LTrim and Trim which are included in the unit Tools.

      Function RTrim (Var S : String) : String ;
      {
         RTrim -- remove trailing blanks
      }
      Var
         i : Byte ;

      begin { RTrim }
         for i := Length(S) downto 1 do
            if S[i] > BLANK then begin
               S     := Copy(S,1,i) ;
               RTrim := S ;
               Exit
            end ;
         {
               if we reach this point then S contains only BLANKS
            so we return a null string
         }
         S     := '' ;
         RTrim := S
      end ; { RTrim }


      Function LTrim (Var S : String) : String ;
      {
         LTrim -- remove leading blanks
      }
      Var
         i : Byte ;

      begin { LTrim }
         for i := 1 to Length(S) do
            if S[i] > BLANK then begin
               S     := Copy(S,i,MAXSTR) ;
               LTrim := S ;
               Exit
            end ;
         {
               if we reach this point then S contains only BLANKS
            so we return a null string
         }
         S     := '' ;
         LTrim := S
      end ; { LTrim }


      Function Trim  (Var S : String) : String ;
      {
         Trim -- remove leading and trailing blanks
      }
      begin { Trim }
         S     := RTrim(S) ;
         S     := LTrim(S) ;
         Trim  := S
      end ; { Trim }

Detabbing

Actor — Tue, 01 Jan 2008 09:08:25 -0700

DeTab is the inverse of EnTab. Here is the specification:

{
PROGRAM
      DeTab    -- convert tabs to blanks
USAGE
      DeTab
FUNCTION
      DeTab copies its input to its output, expanding horizontal tabs to 
      blanks along the way, so that the output is visually the same as the        
      input, but contains no tab chars.  Tab stops are assumed to be set
      every three columns (i.e., 1, 4, 7, 10, ...), so that each tab char
      is replaced by from one to three blanks.
BUGS
      1. DeTab is naive about backspace, vertical motions, and
         non-printing chars.
      2. Each line of output will be truncated at MAXSTR chars.
      3. Trailing BLANKS will be trimmed from each line of output.

}

DeTab's main routine echos EnTab's, reducing the problem to one of detabbing a single string. To detab the string we could try to simply apply EnTab's strategy in reverse, however, this is another chance to apply the "how would a human do it?" approach.

How would a human do it? If a human is sitting at a typewriter typing the incoming text, what is happening? First, he is looking at a blank sheet of paper. At least the current line is blank. If he hits any other than the TAB key the corresponding letter/character gets typed. Even if he hits the space bar a character, a BLANK, gets typed, even though what actually happens is that the carriage moves one space to the left (effectively moving the print head to the right). However, if he hits the TAB key the carriage moves to the left until it hits a tab stop, printing nothing and leaving the print head at the tab stop awaiting the next character.

This is the behavior we will try to emulate. We will copy the input string to an output string. But first we will fill the output string with BLANKS, effectively giving us a blank line. We will use an index i for the input string and j for the output string. If the char is not a TAB then we will copy the char and increment both i and j. However, if it is a TAB we increment i once but we increment j repeatedly until we get to a tab stop.

To deal with the situation of what happens when we encounter a TAB after the last tab stop we cease incrementing j once it exceeds MAXSTR. We also do an early exit from the routine should j exceed MAXSTR. In keeping with our previous philosophy we do not expect this to happen but it could. If it does the program exits cleanly, albeit with a corrupted output. We will simply live with this known bug.

Finally, we trim the end of the output string of any BLANKS. This means that any trailing BLANKS in the input string will not get copied to the output. Strictly speaking this is a bug but it is unlikely to cause problems. Again we will live with it.

The function RTrim gets rid of trailing BLANKS. We will add it to Tools. While we are at it we will also add LTrim, which gets rid of leading BLANKS, and Trim, which does both. I will post the
code next time.

Program DeTab ;
{
   DeTab -- replace blanks with tabs and blanks
}
Uses
   Tools,
   TabsUnit ;

      Procedure DeTabStr (Var S : String) ;
      {
         Detab a string
      }
      Var
         i     :  Byte ;
         j     :  Word ;
         T     :  String ;

      begin { DeTabStr }
         {
            clear target string
         }
         T := '' ;
         while Length(T) < MAXSTR do
            T := T + BLANK ;

         j := 1 ;
         for i := 1 to Length(S) do begin
            if j > MAXSTR then      { not likely but not impossible }
               Break ;                  

            Case S[i] of
               TAB :
                  repeat
                     j := j + 1
                  until (j in TabSet) OR (j > MAXSTR)
               else
                  begin
                     if j <= MAXSTR then
                        T[j]  := S[i] ;
                     j     := j + 1
                  end
            end { Case }
         end ;

         S := RTrim(T)
      end ; { DeTabStr }

Var
   S      :  String ;

begin { DeTab }
   SetTabs ;

   while NOT eof do begin
      ReadLn (S) ;
      DeTabStr (S) ;
      WriteLn (S)
   end
end.  { DeTab }

Entabbing

Actor — Fri, 28 Dec 2007 03:54:10 -0700

The next program in our project is EnTab which replaces runs of blanks in a text file by tabs and blanks. Here is the specification, i.e., the "manual"

PROGRAM
   EnTab -- convert runs of blanks into tabs

USAGE
   EnTab
FUNCTION
   EnTab copies its input to its output, replacing strings of blanks by
   tabs so that the output is visually the same as the input but contains
   fewer characters.  Tab stops are assumed to be set every 3 columns
   (i.e., 1, 4, 7, ...), so that each sequence of one to four blanks
   ending on a tab stop is replaced by a tab character.
BUGS
   1. EnTab is naive about backspaces, vertical motions and non-printing
      characters.
   2. EnTab will convert a single blank to a tab if it occurs at a tab
      stop, thus EnTab is not an exact inverse of DeTab.
   3. if any record in the input is longer than 255 char Entab will
      truncate that record to 255 char.

We first address how tab stops are to be represented in the program. Since we will next write the inverse program DeTab, we choose to write a unit, TabsUnit, to be used by both programs and thus ensure conformity between the two programs.

Here is the code for the unit TabsUnit:

Unit TabsUnit ;
{
   used by DeTab and EnTab
}
interface
   Uses
      Tools ;

   Type
      TabType  =  Set of Byte ;

   Var
      TabSet   :  TabType ;


   Procedure SetTabs ;

implementation

   Procedure SetTabs ;
   {
      SetTabs -- set initial tab stops
   }
   CONST
      TABSPACE = 3 ;    { 3 spaces per tab }

   Var
      i  :  Byte ;

   begin { SetTabs }
      for i := 0 to MAXSTR do
         if i MOD TABSPACE = 1 then
            Include (TabSet, i)
         else
            Exclude (TabSet, i)
   end ; { SetTabs }

end.

As you can see we choose to represent tab stop with a set of byte. Any number in the range 0 .. 255 that is a member of the set is a tab stop. The set is declared to be a user defined type TabType. The unit also declares a variable TabSet : TabType and a procedure SetTabs which sets a tab every three spaces.

Our first cut of the program itself is (in pseudocode) :

Program EnTab

begin
   while not eof
      read a string from standard input
      entab that string
      write the string to standard output
   end
end

This approach reduces the entire problem to one of entabbing a string. By reading in an entire string before entabbing it we are able to access any char in the string at any time and are not forced to deal with the data on-the-fly. The price we pay for this is that our program will not be able to handle records that are longer than the maximum length of a Turbo Pascal
string, 255 chars.

Our experience is that by approaching a programming problem from the viewpoint of how a human being would tackle it we reduce its complexity.
The question becomes "How would a human decide where to put tabs and what blanks to eliminate?" This question already breaks the problem into two parts that we can consider separately

(1)where do we put tabs? Obviously any space that immediately precedes a tab stop is a candidate for replacement by a tab.

(2)what blanks do we eliminate? Having completed the first step we simply delete any and all blanks that immediate precede a tab. Since it is possible, indeed quite likely, that more than one blank will precede a tab this needs to be done in a loop.

Here is our code for EnTab.

Program EnTab ;
{
   EnTab -- replace blanks with tabs and blanks
}
Uses
   Tools,
   TabsUnit ;

      Procedure EnTabStr (Var Str : String) ;
      {
         EnTab a single line
      }
      Var
         i  : Byte ;

      begin { EnTabStr }
         {
            first scan of the string - where to put tabs
         }
         for i := 1 to Length (Str) do
            if (Str[i] = BLANK) AND (i + 1 in TabSet) then
               Str[i]   := TAB ;
         {
            second scan of the string - what blanks to eliminate
         }
         for i := 1 to Length (Str) do
            if Str[i] = TAB then
               while Str[i - 1] = BLANK do begin
                  Delete(Str, i - 1, 1) ;
                  i := i - 1
               end
      end ; { EnTabStr }

Var
   Str      :  String ;
   TabStops :  TabType ;

begin { EnTab }
   SetTabs ;

   while NOT eof do begin
      ReadLn (Str) ;
      EnTabStr (Str) ;
      WriteLn (Str)
   end
end.  { EnTab }

As you can see, by working with a string we are able to scan the record and implant tabs, then [i]back up[/i] and scan the record again to eliminate blanks. You cannot back up if dealing with the data stream on-the-fly.

We have already acknowledged that the program contains a "bug" in not being able to handle records longer than 255 chars. We believe the bug is inconsequential and unlikely ever to manifest itself. If the bug is a problem there are ways to cure it without resorting to on-the-fly
processing. The first is to define a type LongString:

Type
   LongString = Record
      Len   :  Word ;
      LongS :  Array [1 .. 32767] of char
   end ;

Allowing a string up to 32767 char. This approach will require you to write several supporting routines: ReadLongString, WriteLongString, LongLength, LongDelete. You will also have to redefine how tabs are represented and detected since a set can have only 256 members. The simplest would be to have every position after 255 automatically be a tab stop. This suggests that one might be able to rewrite the main routing thus:

begin { EnTab }
   SetTabs ;

   while NOT eof do begin
      Read (Str) ;
      EnTabStr (Str) ;
      Write (Str) ;
      {
         if record is longer than 255 chars
      }
      while NOT eoln do begin
         Read(Ch) ;
         Write(Ch)
      end ;
      {
         move on to next record
      }
      ReadLn ;
      WriteLn
   end
end.  { EnTab }

Leaving the tabs representation and EnTabStr intact.

Finally, you could read each record into a typed file of char, effectively
giving a string representation that could be over two billion char long.
That should be enough for anybody.

I have not written, debugged or tested any code using this approach. I leave that to you.

Elements of Programming Style

Actor — Mon, 03 Dec 2007 11:43:08 -0700

I've always recommended that programmers make it a point to read this classic by Kernighan and Plauger. I'm now in the process of reading it again. I had to request an interlibrary load to get it.

Upon re-reading it (I'm now up to chapter 3) I find it terribly dated. The examples are all in Fortran and PL/1 (PL/I?). One of the "rules" set forth is "avoid the Fortran arithmetic IF," a good piece of advise if you happen to be programming in Fortran but of little use if you are using C++ or Pascal.

The first chapters of the book seem to deal almost exclusively with when and when not to use GOTO and how to use it when you do. Again advise aimed at Fortran programmers who, lacking WHILE and IF..THEN..ELSE, had no choice but to use GOTO, and at PL/1 programs who could avoid the GOTO but often didn't, producing "Fortran with semicolons."

I think the book is still worth a read but I'm not so sure it is still a MUST READ. An updated version with examples in C++, Java and/or Pascal would be good but it's something I doubt the authors would be interested in doing. The very fact that the book seems dated is an indication that the authors accomplished their mission.

Showing tabs

Actor — Sat, 10 Nov 2007 23:03:13 -0700

Some files contain TABs, Chr(9), as a form of modest compression. When a program displaying the file encounters a TAB it prints out a series of one or more blanks. The next two programs insert and remove TABs. To test these programs we will need a program that displays the tabs. This program substitutes a ^ for the tab so we can see the file's true contents.

Program ShowTabs ;
{
ShowTabs -- display tabs in a file.
}
Uses
    Tools ;	{ TAB and CARET ( ^ )}

Var
    Ch :  Char ;

begin { ShowTabs }
    while NOT eof do begin
        Read (Ch) ;
        if Ch = TAB then
            Ch := CARET ;
        Write (Ch)
    end
end.  { ShowTabs }

Counting Words

Actor — Sat, 27 Oct 2007 21:27:52 -0700

The next program counts the words in a file. K&P define a word as "a sequence of any characters except blanks, tabs and newlines." Since we are not using the NEWLINE character we'll redefine it as "a sequence of any characters except blanks, tabs, line feeds and carriage returns."

The algorithm used by K&P is, in my opinion, too complex. It uses a flag, inword, to keep track of whether the file pointer is "in a word", tests that flag, and then changes it, or not, depending on the results of that test.

Consider TAB, LF, CR and BLANK. Let’s call these delimiters. The signal to increment the count is a transition from a delimiter to a non-delimiter. Thus, we need to keep track of the previous character in the stream. The problem of "what was the previous character when we read the first character" is trivial. We need only assign it some value. That value must be a delimiter otherwise the first word in the file will not get counted.

Program WordCnt ;
{
      WordCnt -- count words in standard input
}
Uses
   Tools ;

CONST
   DELIMITERS  :  Set of Char = [TAB, LF, CR, BLANK] ;

Var
   Ch,
   Prev  :  Char ;
   Count :  LongInt ;

begin { WordCnt }
   Prev  := BLANK ;
   Count := 0 ;

   while NOT eof do begin
      Read (Ch) ;
      if (Prev in DELIMITERS) AND (NOT(Ch in DELIMITERS)) then
             Count := Count + 1 ;
      Prev  := Ch
   end ;

   WriteLn (Count:0)
end.  { WordCnt }

Another departure from K&P is the use of a set and a typed constant. Typed constants allow values to be assigned to structured constant types, a feature of Turbo Pascal that K&P did not have access to. The use of a set makes the program more changeable (maintainable) since the choice of delimiters can be changed by changing their definition in line 8. For example

CONST
   NUL = Chr(0) ;
   DELIMITERS  :  Set of Char = [NUL .. BLANK] ;

In this case I would add NUL to the unit Tools (and I will later). DELIMITERS could also be added to Tools but I did not since I do not anticipate using DELIMITERS again. I also anticipate that other programs that use the concept of delimiters would not need the same definition so I kept the definition local.

The Tools Unit

Actor — Sat, 27 Oct 2007 15:59:40 -0700

Before proceeding with the next program let’s skip forward to the index of the book to page 338. Here K&P list the code for their "wrapper." The wrapper is a program which defines constants, types, functions and procedures that are used by their other programs. Here is the explanation of why K&P’s programs are not programs at all but procedures. One implements a program such as charcount by including it in the wrapper and calling it from the wrapper. The wrapper for UCSD Pascal, probably the closest pre Turbo implementation to Turbo Pascal, is given on pages 338 .. 341. Turbo Pascal’s units, i.e., its provision for separate compilation, makes the rigmarole of the wrapper superfluous, although it was probably a good strategy in 1981 a couple of years before Turbo Pascal made the scene.

Instead of a wrapper we’ll create a Turbo Pascal unit called Tools. We’ll start with only what we need and expand it as we go. In anticipation of what we’ll need to write out next program here is our first cut of Tools.

Unit Tools ;
{
   a unit of procedures, functions, constants used in software tools
}
interface

   CONST
      TAB      = Chr(9) ;
      LF       = Chr(10) ;
      CR       = Chr(13) ;
      BLANK    = Chr(32) ;

implementation

end.  { Tools }

Testing LineCnt

Actor — Wed, 24 Oct 2007 19:59:16 -0700

Ascii writes all the classic ascii characters to standard output or, if redirected, to a file. If run without redirection the programs seems to perform as expected. We get all the ascii characters including a line feed, chr(10), and a carriage return, chr(13). However, when we redirect the output to ascii.all and then display ascii.all using type we get considerably less output.

DOS displays various "non printing" characters as various symbols. Chr(1) is a smiley face. Chr(2) is a reverse smiley face. The next four characters, chr(3) .. chr(6) are the four suites of a deck of cards, etc.

The output of ascii.all via type is two lines. The first is short, ending with a diamond. Then other characters do not print but actually do something. Chr(7) gives us a beep. Chr(8) backspaces.

Of particular interest is chr(10), a line feed, which causes the cursor to drop down a line, and chr(13), a carriage return, which sends the cursor to the left edge of the screen causing subsequent characters to overwrite whatever was there.

When we get to chr(25) we get an arrow pointing down and the output terminates. Why? Because DOS uses the next char, chr(26), as end-of-file. Thus when we redirect output to ascii.all that’s as far as we get. When we use type to look at the file, that’s all there is.

On page 16 K&P present the following exercise.

"What happens if the last character of input to linecount is not a NEWLINE? Does the program stay sane? Is its behavior a bug or a natural consequence of our definition of a 'line'?"

ascii.all is just such a file, one whose last character is not a NEWLINE (CR + LF).

Linecnt < ascii.all

The answer is two. Why? Because the first ReadLn reads until it finds the carriage return. The second reads until it finds the end of file. In my opinion the output is sane and correct, and the behavior is not a bug.

I think K&P’s version would behave the same way if implemented in Turbo Pascal. Other implementations of Pascal might give different results.

Mystery program

Actor — Tue, 23 Oct 2007 23:24:53 -0700

This may seem like a digression but it’s not. I have a point to make regarding our progress up to now.

Consider the following program.

Program Ascii ;
{
   outputs all the ascii chars ... maybe
}
Var
   i  : Byte ;

begin { Ascii }
   for i := 0 to 127 do
      Write (Chr(i))
end.  { Ascii }

Compile and run the program. What is the output?

Now redirect the output to a file, then use the type command to list the output.

ascii > ascii.all

type ascii.all

Why is the output different? Answer tomorrow.

Counting Lines

Actor — Mon, 22 Oct 2007 17:50:04 -0700

The next program counts the number of lines in a text file. My version takes advantage of the fact that ReadLn without a parameter list will move the file pointer past the next CR,LF (new line). Thus the program does not even have to know about the intervening chars. The result is a shorter and more elegant program.

Program LineCnt ;
{
      count lines in standard input
}
Var
   Count : LongInt ;

begin { LineCnt }
   Count := 0 ;	
   while NOT eof do begin
      ReadLn ;
      Count := Count + 1
   end ;
   WriteLn (Count:0)
end.  { LineCnt }

I declare Count as a LongInt, a type that K&P did not have access to. I also used LongInt as the counter in CharCnt. It allows the programs to work with much larger files.

As an interesting exercise try omitting the line

Count := 0

which initializes the counter. This should be a bug but I discovered long ago that the programs still work. It apparently is an undocumented feature of Turbo Pascal that integers get initialized to zero by default. Now that I know about it I try never to use it. It goes against the spirit of defensive coding.

Counting Characters

Actor — Mon, 22 Oct 2007 10:54:38 -0700

The next program counts the number of characters in a file. The most noteworthy difference between the K&P version and this one is that a new line counts as 2 characters because in DOS it is two characters. Also my program is named CharCnt because the K&P name, charcount, is too long for a DOS name.

Program CharCnt ;
{
      count characters in standard input
}
Var
   Count : LongInt ;
   Ch    : Char ;

begin { CharCnt }
   Count := 0 ;

   while NOT eof do begin
      Read (Ch) ;
      Count := Count + 1
   end ;

   WriteLn (Count:0)
end.  { CharCnt }

I have used Pascal's WriteLn procedure for output instead of K&P's putdec mainly because at this point, page 13, K&B have not gotten around to defining putdec.

Look up the K&P version at

http://cm.bell-labs.com/cm/cs/who/bwk/pascaltools.txt

and search for "charcount"

Testing

Actor — Sun, 21 Oct 2007 13:41:56 -0700

If you run Kopy and input data from the keyboard you get an output something like this:

Now is the time for all good men
Now is the time for all good men
to come to the aid of their country.
to come to the aid of their country.
^Z

The lines come in pairs. The first line is the echoing of the keyboard input; the second line is the program output. The program terminates on end of file, chr(26), which is CTRL Z on the keyboard and is echoed as ^Z. The program does not output this.

Using Kopy to copy files requires redirection.

Kopy < kopy.pas > kopy.txt

This copies kopy.pas to kopy.txt.

fc kopy.pas kopy.txt

reveals that the two files are identical.

I will test all programs but will not always post the results.

Getting Started - File Copying

Actor — Thu, 18 Oct 2007 23:24:17 -0700

At the outset Kernighan and Plauger present their readers with a user defined type character which is defined as

type
	character = -1..127;   { ASCII, plus ENDFILE }

The only purpose of type character is to defeat Pascal strong typing by mapping the ASCII character set onto a subset of integers. I do not think this is a good idea. K&P apparently do not like strong typing. I disagree. I believe that strong typing is a virtue, not a vice, therefore all the programs which I present will use Pascal’s type char, not character.

Having established type character K&P then define two constants

const
	ENDFILE = -1;
	NEWLINE = 10;	{ ASCII value }

DOS uses chr(26) for end of file and chr(13) for end of line. If I have occasion to use either ENDFILE or NEWLINE they will be defined accordingly (as char, not integer).

K&P then define two "primitive" functions: getc and putc. More precisely

function getc(var c : integer) : integer ;

and its inverse

function putc(c : integer) ;

getc and putc serve as K&Ps basic input/output functions. Why Read and Write are not adequate is never made clear. getc and putc simply serve to force an unneeded C-like syntax onto Pascal. (Kernighan is credited with being the co-inventor of C.) I see no need for getc and putc. For an experienced Pascal programmer they not only generate more code but work againse K&P’s declared objective (on the cover of the book) to make programs "...clean, easy to read,..." This is an issue which I have given much thought. The programs I present will not use getc or putc.

To illustrate my reservations about getc and putc consider copy, the first program K&P present. Copy duplicates the function of the DOS copy command and as such is merely academic, tutorial or pedagogic (choose your own adverb). Here's their version:

{ Copyright (C) 1981 by Bell Laboratories, Inc., and Whitesmiths Ltd. }
{ copy -- copy input to output }
procedure copy;
var
	c : character;
begin
	while (getc(c) <> ENDFILE) do
		putc(c)
end;

First note that this is a procedure, not a program. The reason for this is not made clear until the end of the book.

while (getc(c) <> ENDFILE) do

To an experienced Pascal programmer this line works against the objective of creating readable code. Too much is happening on one line, and it’s not even happening left to right (or top to bottom); it’s happening inside out. getc is the first thing executed (on the inside) and then a logical test is made. K&P are trying to force C syntax onto Pascal. Yes, this is a criticism of C and I’m not the first to make it.

Here's my version:

Program Kopy ;
{
    Kopy -- copy input to output
}
Var
    Ch : Char ;
begin { Kopy }
    while NOT eof do begin
        Read (Ch) ;
        Write (Ch)
    end
end.  { Kopy }

Notes:

It's a program, not a procedure.

It's called Kopy, not copy. I don't want my program to collide with the DOS command copy.

The first line of executable code

while NOT eof do begin

will be familiar to Pascal programmers, an old friend. Readability is enhanced by familiarity.

What happens when Kopy encounters the end of line? End of line in DOS is a combination of a carriage return {Chr(13)} followed by a line feed {Chr(10)}. It is a virtue of Turbo Pascal that, if one ignores (does not test for) end of line, it will return chr(13) and chr(10) in turn. Eoln is actually a test that returns TRUE whenever the next (unread) character in the stream is a carriage return. Kopy does not test for eoln. There’s no need.

In which I name the game

Actor — Thu, 18 Oct 2007 22:24:32 -0700

Software Tools in Pascal is a rewrite of Software Tools by Brian W. Kernighan and P. J. Plauger. In the first book Kernighan and Plauger wrote their programs in RatFor, a dialog of Fortran implemented via a preprocessor, which gave Fortran a C-like syntax. In attempting to repeat this effort using Pascal, Kernighan apparently developed a dislike for the language and in the same year Software Tools in Pascal was published he also published his famous rant Why Pascal is Not My Favorite Programming Language. I will address this rant in a later post.

My intention here is to re-write the programs in Software Tools in Pascal using Turbo Pascal, an implementation of the language that became a de-facto standard. I will admit up front that this effort is entirely academic. I'm doing it for fun. Still, some people might find it useful. The tools K&P presented were, even at that time, pretty much available pre-packaged in DOS and Unix, so even the original books were something of an academic effort.

In using Turbo Pascal I avoid one of the issues of K&P's effort, an attempt to write programs that were implementation independent. Rather, I embrace Turbo Pascal, an implementation which has become a de-facto standard, and make full use of its features and improvements of the original language. Technically this means portability is sacrificed. In practice the programs will run on a majority of DOS/Windows machines.

In particular I will make use of Turbo Pascal's string handling features. The ASCII character set is used exclusively. I will also make extensive use of Turbo Pascal’s units, i.e., separate compilation and reuse of code.

I encourage anyone who follows along on this adventure to obtain a copy of Software Tools in Pascal. The ISBN is 0-201-10342-7. It's very cheap when purchased used. Alternatively the code can be found online at

http://cm.bell-labs.com/cm/cs/who/bwk/pascaltools.txt

I will post small pieces of the code here simply to make it easier for the reader to follow along. This is common practice in academic circles and does not violate any copyright, a fact that I hope the owners of this web site appreciate.