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
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
|
Network Working Group R. Anderson
Request for Comments: 83 A. Harslem
NIC: 5621 J. Heafner
RAND
18 December 1970
LANGUAGE-MACHINE FOR DATA RECONFIGURATION
Introduction
In NWG/RFC #80 we mentioned the needs for data reconfiguration along
with a complier/executor version of a Form Machine to perform those
manipulations.
This note proposes a different approach to the Form Machine.
Specifically, we describe a syntax-driven interpreter that operates
on a grammar which is an ordered set of replacement rules. Following
the interpreter description are some "real-world" examples of
required data reconfigurations that must occur between RAND consoles
and the Remote Job System on the UCLA 360/91. Lastly, we suggest
that the Protocol Manager mentioned in NWG/RFC #80 can be simplified
by using the Form Machine and two system forms (specified a priori in
the code).
Caveat: The Form Machine is not intended to be a general purpose
programming language. Note the absence of declaration statements,
etc.
THE FORM MACHINE
I. Forms
A form is an ordered set of rules.
F = {R1, ...,Rn}
The first rule (R1) is the rule of highest priority; the last rule
(Rn) is the rule of lowest priority.
The form machine gets as input: 1) a list of addresses and lengths
that delimit the input stream(s); 2) a list of addresses and lengths
that delimit the output area(s); 3) a pointer to a list of form(s);
4) a pointer to the starting position of the input stream; and 5) a
pointer to the starting position of the output area. The Form
Machine applies a form to the input string emitting an output string
in the output area. The form is applied in the following manner:
Anderson, et. al. [Page 1]
^L
RFC 83 Language Machine For Data 18 December 1970
Step 1: R1 is made the current rule.
Step 2: The current rule is applied to the input data.
Step3: a) If the rule fails, the rule of priority one lower is
made current.
b) If the rule succeeds, the rule of highest priority is
made current
c) When the rule of lowest priority fails, the form fails
and application of the form to the input data
terminates.
Step 4: Continue at Step 2.
In addition, during Step 2, if the remainder of the input string is
insufficient to satisfy a rule, then that rule fails and partial
results are not emitted. If a rule fills the output string,
application of the form is terminated.
II. Rules
A rule is a replacement operation of the form:
left-hand-side -> right-hand-side
Both sides of a rule consists of a series of zero or more _terms_
(see below) separated by commas.
The left-hand-side of the rule is applied to the input string at the
current position as a pattern-match operation. If it exactly
describes the input, 1) the current input position pointer is
advanced over the matched input, 2) the right-hand-side emits data at
the current position in the output string, and 3) the current output
position pointer is advanced over the emitted data.
III. Terms
A term is a variable that describes the input string to be matched or
the output string to be emitted. A term has three formats.
Anderson, et. al. [Page 2]
^L
RFC 83 Language Machine For Data 18 December 1970
Term Format 1
+---------------------------------------------------------------------+
| |
| name ( data replication . value : length ) |
| type expression expression expression |
| |
|_____________________________________________________________________|
Any of the fields may be absent.
The _name_ is a symbolic name of the term in the usual programming
language sense. It is a single, lower-case alphabetic that is unique
within a rule.
The _data type_ describes the kind of data that the term represents.
It is a member of the set:
{D, O, X, A, E, B}
Data types have the following meanings and implied unit lengths:
Char. Meaning Length
----- -------- -------
D decimal number 1 bit
O octal number 3 bits
X hexadecimal number 4 bits
A ASCII character 8 bits
E EBCDIC character 8 bits
B binary number 1 bit
The _replication expression_ is a multiplier of the value expression.
A replication expression has the formats.
1) an arithmetic expression of the members of the set:
{v(name), L(name) , numerals, programming variables}
The v(name) is a value operator that generates a numeric value of
the named data type and L(name) is a length operator that
generates a numeric value of the named string length.
The programming variable is described under term format three.
Arithmetic operators are shown below and have their usual
meanings.
{*, /, +, -}
Anderson, et. al. [Page 3]
^L
RFC 83 Language Machine For Data 18 December 1970
or 2) the terminal '#' which means an arbitrary multiple of the value
expression.
The _value expression_ is the unit value of a term expressed in the
format indicated by the data type. The value expression is repeated
according to the replication expression. A value expression has the
format:
1) same as part 1) of the replication expression where again
v(name) produces a numeric value
or 2) a single member of the set
{v(name), quoted literal}
where v(name) produces a data type (E or A) value). (Note that
concatenation is accomplished through multiple terms.)
The _length expression_ is the length of the field containing the
value expression as modified by the replication expression. It has
the same formats as a replication expression.
Thus, the term
x(E(7.'F'):L(x)) is named x, is of type EBCDIC, has the value
'FFFFFFF' and is of length 7.
The term
y(A:8) on the left-hand-side of a rule would be assigned the next
64 bits of input as its value; on the right-hand-side it would
only cause the output pointer to be advanced 64 bit positions
because is has no value expression (contents) to generate data in
the output area.
Anderson, et. al. [Page 4]
^L
RFC 83 Language Machine For Data 18 December 1970
Term Format 2
+---------------------------------------------------------------------+
| |
| name (label) |
| |
+---------------------------------------------------------------------+
The _label_ is a symbolic reference to a previously named term in the
rule. It has the same value as the term by that name.
The identity operation below illustrates the use of the _label_
notation.
a(A:10) -> (a)
The (a) on the right-hand side causes the term a to be emitted in the
output area. It is equivalent to the rule below.
a(A:10) -> (Av(a):L(a))
Term Format 3
+---------------------------------------------------------------------+
| |
| name ( programming connective operand ) |
| variable expression |
| |
+---------------------------------------------------------------------+
A _programming variable_ is a user-controlled data item that does not
explicitly appear in the input/output streams. Its value can be
compared to input data, to constants, and used to generate output
data. Programming variables are single, lower case Greek symbols.
They are used: to generate indices, counters, etc. in the output
area; to compare indices, counters, etc. in the input area, and; to
bind replacement rules where the data is context sensitive (explained
later).
A _connective_ is a member of the set:
{<-, =, !=, >=, <=, <, >}
The left arrow denotes replacement of the left part by the right
part; the other connectives are comparators.
Anderson, et. al. [Page 5]
^L
RFC 83 Language Machine For Data 18 December 1970
The _operand expression_ is an arithmetic expression of members of
the set:
{programming variables, v(name), l(name), numerals}
For example, if the programming variable [alpha] has the value 0 and
the rule
a(H[alpha]:1) -> (a), ([alpha]<-[alpha]+1), (H[alpha]:1)
is applied exhaustively to string of hexadecimal digits
0 1 2 3 4 5
the output would be the hexadecimal string
0 1 1 2 2 3 3 4 4 5 5 6 .
Note: the above rule is equivalent to
a(B[alpha]:4) -> (a), ([alpha]<-[alpha]+1), (B[alpha]:4)
IV. Restrictions and Interpretations of Term Functions
When a rule succeeds output will be generated. In the rule
a(A:#),(A'/':1)->(Ev(a):74),(E'?':1)
the input string is searched for an arbitrary number of ASCIIs
followed by a terminal '/'. The ASCIIs (a) are converted to EBCDIC
in a 74-byte field followed by a terminal '?'. This brings out three
issues:
1. Arbitrary length terms must be separated by literals since the
data is not type-specific.
2. The # may only be used on the left-hand-side of a rule.
3. A truncation padding scheme is needed.
Anderson, et. al. [Page 6]
^L
RFC 83 Language Machine For Data 18 December 1970
The truncation padding scheme is as follows:
a. Character to Character (types: A, E)
Output is left-justified with truncation or padding (with
blanks) on the right.
b. Character to Numeric (A, E to D, O, H, B)
c. Numeric to Character (D, O, H, B to A, E)
d. Numeric to Numeric (D, O, H, B)
Output is right-justified with padding or truncation on the
left. Padding is zeros if output is numeric.
EXAMPLES OF SOME DATA RECONFIGURATIONS
The following are examples of replacement rule types for specifically
needed applications.
Literal Insertion
To insert a literal, separate the left-hand-side terms for its
insertion on the right.
a(A:10),b(A:70)->(a),(E'LIT':3),(b)
The 80 ASCII characters are emitted in the output area with the
EBCDIC literal LIT inserted after the first 10 ASCII characters.
Deletion
Terms on the left are separated so that the right side may omit
unwanted terms.
(B:7),a(A:10)->(Ev(a):L(a))
Only the 10 ASCII characters are emitted (as EBCDIC) in the output
area, the 7 binary digits are discarded.
Spacing in the Output Buffer
Where a pre-formatted output buffer exists (typically a display
buffer) spacing can be realized by omitting the replication and
value functions from a term on the right.
Anderson, et. al. [Page 7]
^L
RFC 83 Language Machine For Data 18 December 1970
a(A:74)->(E:6),(Ev(a):74)
The (E:6) causes 48 bit positions to be skipped over in the output
area, then the 74 ASCII characters are converted to EBCDIC and
emitted at the current output position.
Arbitrary Lengths
Some devices/programs generate a variable number of characters per
line and it is desirable to produce fixed-length records from
them.
a(A:#) -> (Ev(a):74)
The ASCII characters are truncated or padded as required and
converted to EBCDIC in a 74 character field.
Transposition
Fields to be transposed should be isolated as terms on the left.
a(X:2),b(A:#)->(Ev(b):L(b)),(a)
String Length Computation
Some formats require the string length as part of the data stream.
This can be accomplished by the length function.
a(E:10),b(X'FF':2)->(BL(a)+L(b)+8:8),(Av(a):L(a)),(b)
The length term is emitted first, in a 8 bit field. In this case
the length includes the length field as well as the ASCII
character field.
Expansion and Compression of repeated Symbols
The following rule packs repeated symbols.
a(E:1), b(E#*v(a):L(b)) -> (BL(b)+1:8),(a)
Given the input string below, three successive applications of the
rule will emit the output string shown.
Input: XXXXYYZZZZZZZ
Output: 4X2Y7Z
Anderson, et. al. [Page 8]
^L
RFC 83 Language Machine For Data 18 December 1970
APPLICATION OF THE FORM MACHINE TO PROGRAM PROTOCOLS
The Protocol Manager mentioned in NWG/RFC #80 needs several
interesting features that are properties of the above Form Machine.
In certain instances during a protocol dialog it might be acceptable
to get either an accept on connection A or an allocation on connect
B, that is, the order is sometimes unimportant. The defined
procedure for applying rules allows for order independence.
A logger might send us a socket number embedded in a regular message
-- the socket number is intended to be the first of a contiguous set
of sockets that we can use to establish connections with some
program. We wish to extract the socket number field from the regular
message, perhaps convert it to another format, and add to it to get
the additional socket names. As a result of the regular message we
wish to emit several INIT system calls that include the socket
numbers that we have computed. The value operator and the arithmetic
operators of the Form Machine can do this.
A third property of the Form Machine that is applicable to protocols
is inter- and intra-rule binding to resolve context sensitive
information. In general we wish rules to be order independent but in
certain cases we wish to impose an ordering. Using the logger in
NWG/RFC #66 as an example, the close that is sent by the logger can
have two different meanings depending upon its context. If the close
is sent before the regular message containing the socket number then
it means call refused. If the regular message precedes the close
then the call is accepted. Since the close has contextual meaning,
we must bind it to the regular message to avoid introducing IF and
THEN into the Form Machine language.
Assume for a moment that we can express system calls in Form Machine
notation. (The notation below is for _illustration only_ and is not
part of the Form Machine language.) We have two ways to bind the
regular message to the close. By intra-rule binding we insist that
the close be preceded by a regular message.
Reg. Msg , Close ->
Now assume for a moment that the remote party must have an echo after
each transmission. Since we must emit an echo after receiving the
regular message and before the close is sent, then we must use
inter-rule binding. This can be accomplished with the programming
variable. It is assigned a value when the regular message is
received and the value is tested when the close is received.
Reg. Msg -> Echo , ([lambda]+1)
Anderson, et. al. [Page 9]
^L
RFC 83 Language Machine For Data 18 December 1970
Close, ([lambda]=1) ->
To illustrate inter-rule binding via the programming variable the
connection protocol in NWG/RFC #66 could be represented by passing
the following form to a protocol manager. (The notation below is for
_illustration only_ and is not part of the Form Machine language).
1. ->INIT(parameters) , ([alpha]<-0)
Send an INIT(RTS).
2. INIT(parameters) -> ALLOCATE(parameters)
Send an allocate in response to the connection completion (an STR
received).
3. Reg. Msg (parameters) -> ([alpha]<-1)
When the messages bearing link numbers is received, set an
internal indicator. (The extraction of the link is not
illustrated.)
4. CLOSE(parameters),([alpha]=1) ->
INIT(parameters),INIT(parameters)
When the close is received following the regular message [2] is
checked to see that the regular message was received before
establishing the duplex connection. If the close is received with
no regular message preceding it (call refused) the form will fail
(since no rules is satisfied).
This protocol can be handled via a single form containing four
replacement rules. We have examined similar representations for more
complex protocol sequences. Such protocol sequences, stored by name,
are an asset to the user; he can request a predefined sequence to be
executed automatically.
Anderson, et. al. [Page 10]
^L
RFC 83 Language Machine For Data 18 December 1970
Two System Forms to Handle Protocol Statements
Assume that we have a Protocol Manager that manages protocol
sequences between consoles and the Network. The consoles generate
and accept EBCDIC character strings and the Network transmits binary
digits. The console user has a language similar to system calls in
which he can create and store protocol sequences via Protocol
Manager, and at the same time he can indicate which commands are
expected to be sent and which are to be received. Upon command the
Protocol Manager can execute this sequence with the Network,
generating commands and validating those received. Assume also that
the Protocol Manager displays the dialog for the console user as it
progresses.
In order to translate between console and Network for generating,
comparing, and displaying commands, the Protocol Manager can use the
Form Machine. Two system forms are needed, see Fig. 1. One is a
console-to-Network set of rules containing EBCDIC to binary for all
legal commands; the other is a mirror image for Network-to-console.
REQUEST
Since language design is not our forte, we would like comments from
those with more experience than we.
Anderson, et. al. [Page 11]
^L
RFC 83 Language Machine For Data 18 December 1970
System form:
C -> N
+----------+
| one rule |
| for each |
| legal |
| command |
+-------|- - - - - |<----+
| +----------+ |
Binary | | EBCDIC
| |
+----------+ | | +----------+
| |<---+ +------| |
| Network | | Consoles |
| |----+ +----->| |
+----------+ | | +----------+
| Binary EBCDIC |
| |
| |
| System form: |
| N -> C |
| +----------+ |
+------>|- - - - - |-----+
| one rule |
| for each |
| legal |
| response |
+----------+
Figure 1 -- Application of System Form for Protocol Management
Anderson, et. al. [Page 12]
^L
RFC 83 Language Machine For Data 18 December 1970
Distribution List
-----------------
Alfred Cocanower - MERIT
Gerry Cole - SDC
Les Earnest - Stanford
Bill English - SRI
James Forgie - Lincoln Laboratory
Jennings Computer Center - Case
Nico Haberman - Carnegie-Melon
Robert Kahn - BB&N
Peggy Karp - MITRE
Benita Kirstel - UCLA
Tom Lawrence - RADC/ISIM
James Madden - University of Illinois
George Mealy - Harvard
Thomas O'Sullivan - Raytheon
Larry Roberts - ARPA
Ron Stoughton - UCSB
Albert Vezza- MIT
Barry Wessler - Utah
[The original document included non-ASCII characters. The Greek
letters Alpha and Lambda have been spelled out and enclosed in
square brackets "[ ]". A curly "l" character
has been replaced by capital L. Left and right arrows have been
replaced by "<-" and "->" respectively. RFC-Editor]
[This RFC was put into machine readable form for entry]
[into the online RFC archives by Lorrie Shiota, 10/01]
Anderson, et. al. [Page 13]
^L
|