GENWiki

Premier IT Outsourcing and Support Services within the UK

User Tools

Site Tools

Problem, Formatting or Query -  Send Feedback

Was this page helpful?-10+1


rfc:rfc83

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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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]

/data/webs/external/dokuwiki/data/pages/rfc/rfc83.txt · Last modified: 2002/03/04 20:25 (external edit)