1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
|
Example 01: Palindrome filter
In this appendix we illustrate the CLiP style of literate programming by a
program to filter palindromic lines from an input file.
Two files are involved: the program module (*PALINDROME.PAS*) and a test
file (*TESTDATA.IN*).
A.1. Specification
A palindrome is a sentence with the property that the letters from left to
right, read the same as from right to left. In the comparison uppercase and
lowercase letters are considered to be equivalent and all other characters are
simply ignored. Hence an empty sentence is a palindrome. Other examples are:
(************* #file "TESTDATA.IN" #comment off **************)
Ada
1234567
doremifasolosafimerod
(******* Testdata #multiple *******)
(***************** End of TESTDATA.PAS ************************)
The following sentences do not qualify as a palindrome.
(******* Testdata #quick *******)
Mr. Clinton won the elections over Mr. Bush.
This line is not palindromic.
Aabbccdd Aabbccdd Aabbccdd Aabbccdd
Abracadabra
supercalafragilisiticexpielecdosia
The following are examples of more sophisticated palindromes.
(******* Testdata #quick *******)
Able was I, ere I saw Elba.
A man, a plan, a canal, Panama.
Norma is as selfless as I Am, Ron.
Note that the famous Dutch sentence
(******* Testdata #quick *******)
Koos Eekfeen keek maar door rood kerkraam, maar krek door rood raam keek
neef Kees ook.
will not be recognized as a plindrome since it occupies two lines.
The program *PALINDROME* reads an input file, filters the lines that are
palindromic and writes them to an output file.
A.2. Communication with the outside world
The program conforms to the general template of a Pascal program. We introduce
the files *IN_FILE* and *OUT_FILE* to define its communication with the outside
world. The actual files have to be specified at run-time. Thus we have
(*************** #file "PALINDROME.PAS" ***********************)
(****************************************************************)
(* Program: Palindrome filter program. *)
(* Purpose: To filter the palindromic lines from a given input *)
(* file to a specified output file. *)
(****************************************************************)
PROGRAM PALINDROME (INPUT, OUTPUT, IN_FILE, OUT_FILE);
(******* Palindrome constants #multiple #comment off *******)
(******* Palindrome types #multiple #comment off *******)
VAR
IN_FILE, OUT_FILE: TEXT;
(******* Palindrome variables #multiple #comment off *******)
BEGIN
OPEN (IN_FILE, 'TESTDATA.IN', HISTORY := OLD); RESET (IN_FILE);
OPEN (OUT_FILE, 'TESTDATA.OUT', HISTORY := NEW); REWRITE (OUT_FILE);
(***************** Palindrome (body) **********************)
(** Copy the lines of the IN_FILE that are palindromic to **)
(** the OUT_FILE. **)
(************************************************************)
END (*PALINDROME*).
(******************* End of PALINDROME.PAS ********************)
To prepare the module for future declarations of constants and types we have
(******* Palindrome constants #leader #quick *******)
CONST
(******* Palindrome types #leader #quick *******)
TYPE
A.3. Processing of the files
The program processes *IN_FILE* line by line. The idea is to buffer an exact
copy of the current line in *IN_LINE*, while at the same time its letters are
buffered in *LETTERS*. So *LETTERS* will be empty if the line holds no letters
at all, in which case the line is considered to be palindromic by definition.
We choose the buffers *IN_LINE* and *LETTERS* to be of the same type, *
TEXT_LINE*, which we will not specify in detail right now. For this purpose we
introduce a type *ABSTRACT*.
(******* Palindrome types #quick *******)
ABSTRACT = (DEFINED, UNDEFINED);
*TEXT_LINE* will temporarily be declared *ABSTRACT* and its details will be
defined later. Thus the declaration of *TEXT_LINE*
(******* Palindrome types *******)
(******* Declaration of TEXT_LINE *******)
(***************** End of Palindrome types ********************)
is temporarily satisfied with the type *ABSTRACT*.
(******* Declaration of TEXT_LINE #quick #default *******)
TEXT_LINE = ABSTRACT;
The declaration for the variables *IN_LINE* and *LETTERS* becomes
(******* Palindrome variables #quick *******)
IN_LINE,
LETTERS: TEXT_LINE;
We have to test *LETTERS* in order to decide whether or not *IN_LINE* contains
a palindrome. The result of this test is flagged by *IS_PALINDROME*, for which
we introduce the declaration
(******* Palindrome variables #quick *******)
IS_PALINDROME: BOOLEAN;
Now the body of the Palindrome filter may be expanded as
(***************** Palindrome (body) **********************)
(** Copy the lines of the IN_FILE that are palindromic to **)
(** the OUT_FILE. **)
WHILE NOT EOF (IN_FILE) DO
BEGIN
(***************** Palindrome (1) *********************)
(** Read a line from IN_FILE into IN_LINE. The letters **)
(** of this line are copied to LETTERS. **)
(********************************************************)
READLN (IN_FILE);
(***************** Palindrome (2) *********************)
(** Test palindromicity of LETTERS. Set IS_PALINDROME **)
(** to reflect the result of the test. **)
(********************************************************)
IF IS_PALINDROME THEN
BEGIN
(***************** Palindrome (3) *****************)
(** Write IN_LINE to OUT_FILE. **)
(****************************************************)
WRITELN (OUT_FILE);
END (*IF*);
END (*WHILE*);
(************* End of Palindrome (body) *******************)
A.4. Choosing the structure of *IN_LINE* and *LETTERS*
Before we can proceed we need to establish a structure for the objects *IN_LINE*
and *LETTERS*. Thus we define *TEXT_LINE* as a structure with two components.
The first component is an array, *CHARS*, which contains the characters to be
buffered. The second component, *LENGTH*, indicates which part of the array is
actually occupied. The maximum number of characters that can be buffered by the
structure is determined by the length, *MAX_L*, of the array. *MAX_L* serves as
an implementation parameter.
(******* Palindrome constants #quick *******)
MAX_L = 132;
(******* Declaration of TEXT_LINE #quick *******)
TEXT_LINE = RECORD
CHARS: ARRAY[1..MAX_L] OF CHAR;
LENGTH: 0..MAX_L;
END (*RECORD*);
A.5. Reading a line
For efficiency reasons we fill *IN_LINE* and *LETTERS* simultaneously.
Therefore we buffer every character that is read from *IN_FILE* in the variable
*IN_CHAR*.
(******* Palindrome variables #quick *******)
IN_CHAR: CHAR;
Only when *IN_CHAR* turns out to be a letter it is copied to *LETTERS*. Since
this process is crucial for the overall operation, we make provisions for some
debugging code here.
(***************** Palindrome (1) *********************)
(** Read a line from IN_FILE into IN_LINE. The letters **)
(** of this line are copied to LETTERS. **)
IN_LINE.LENGTH := 0;
LETTERS.LENGTH := 0;
WITH IN_LINE DO
WHILE NOT EOLN (IN_FILE) DO
BEGIN
READ (IN_FILE, IN_CHAR);
LENGTH := LENGTH + 1;
CHARS[LENGTH] := IN_CHAR;
IF IN_CHAR IN ['A'..'Z', 'a'..'z'] THEN
WITH LETTERS DO
BEGIN
LENGTH := LENGTH + 1;
CHARS[LENGTH] := IN_CHAR;
END (*WITH/IF*);
END (*WHILE/WITH*);
(********************* Palindrome (test) **************)
(** Check contents of IN_LINE and LETTERS. #optional **)
(********************************************************)
(***************** End of Palindrome (1) **************)
A.6. Testing for palindromicity
We test the palindromicity of *LETTERS* in two steps. First we transform the
contents of *LETTERS* to uppercase and then we compare the characters of *
LETTERS* pairwise. The comparison is done starting with the most outside
characters and progressing inward. The string is assumed a palindrome until the
opposite is proven through a pair of different characters. With the local
counter
(******* Palindrome variables #quick *******)
I: INTEGER;
we keep track of the comparing process. Now *Palindrome (2)* can be expanded as
(***************** Palindrome (2) *********************)
(** Test palindromicity of LETTERS. Set IS_PALINDROME **)
(** to reflect the result of the test. **)
WITH LETTERS DO
BEGIN
(* Transform lowercase to uppercase. *)
FOR I := 1 TO LENGTH DO
IF CHARS[I] IN ['a'..'z']
THEN CHARS[I] :=
CHR(ORD(CHARS[I]) - ORD('a') + ORD('A'));
(* Perform the palindromicity test. *)
IS_PALINDROME := TRUE;
I := 1;
WHILE IS_PALINDROME AND (I <= LENGTH DIV 2) DO
IF CHARS[I] = CHARS[LENGTH-I+1] THEN
I := I + 1
ELSE
IS_PALINDROME := FALSE;
END (*WITH*);
(***************** End of Palindrome (2) **************)
A.7. Writing the palindrome
The only remaining action is to write the contents of *IN_LINE*. Again we need
a local counter
(******* Palindrome variables #quick *******)
J: INTEGER;
The writing proceeds straight forward.
(***************** Palindrome (3) *****************)
(** Write IN_LINE to OUT_FILE. **)
WITH IN_LINE DO
BEGIN
FOR J := 1 TO LENGTH DO
WRITE (OUT_FILE, CHARS[J]);
END (*WITH*);
(************* End of Palindrome (3) **************)
|
