User:Art Anger/FlowTree

From J Wiki
Jump to: navigation, search

Data-flow tree depiction

Introduction

http://www.jsoftware.com/jwiki/ArtAnger/FlowTree

The script File:Aatrace.ijs is an expansion of script trace.ijs, as distributed with j602, to include:

-> flowtree y	produces a diagram showing the relationships among each
   x flowtree y	argument, operation, and intermediate result in a single
		expression, as associated by the rules of syntax;
		options may be provided in x.

This presentation differs in orientation and operation placement from that of system function 5!:4 . It will also show the steps of an evaluation even when all operands are provided.

Because the syntactic nature of a name can change during a computation, a statement being parsed has to be executed as the report is being generated. Any name not defined by the time of use will be diagrammed as a verb.

   spendcodes_jtrace_=: 'abjlCERPSU'      [ con_jtrace_=: 3      [ pers_jtrace_=: 'a'
   flowtree '(con= 0) +. pers e. 1+ spendcodes i. ''aCERPSUb'''

             spendcodes 'aCERPSUb'
                  └────┬─────┘
           1          i.
           └─────┬─────┘
con 0 pers       +
 └┬─┘   └───┬────┘
  =        e.
  └────┬────┘
      +.
       │

The tree depicts a generally downward flow of information (data). An arithmetic formula may be read from left to right, interpreted in J from right to left, and listed from innermost to outermost in the tree form. Where sub-expressions evaluate independently, they appear in their original relative left-right relationship, but perhaps at different levels.

People familiar with machine-register loading or "reverse-Polish" notations may not find this view too unsettling. It is also used in "data-pipeline" programming, where processing of a succession of records (or atoms or rows or layers) is described as a funneling of the data to workstations or agents which perform their individual tasks and pass the results down the pipe. Separate streams may join, as with dyadic verbs in J. A flow can be split by copying the data to an alternate stream, as performed by Hook or Fork in J. A holding tank or buffer, collecting a whole stream before releasing any results, is effected in J by infinite-rank operations such as Sort, At, and the &.: version of Under. Some selections, like Infix, and finite-rank applications perform partial bufferings at the relevant levels of data aggregation.

   NB. Piece of cross product of vector pair (v0,: v1) using Fork verb trains
   v0_jtrace_=. 0 0 1     [ v1_jtrace_=. 0 1 0
   flowtree '(((1: |. {.)* (_1: |. {:))- ((_1: |. {.)* (1: |. {:))) v0,: v1'

                         v0 v1
                          └,:┘
                            │
└┬F─┬─F─┬─F─┬─F─┬─F─┬─F─┬F─┬┘
1: {.  _1: {:  _1: {.  1: {:
 └┬─┘   └─┬─┘   └─┬─┘   └┬─┘
 |.      |.      |.     |.
  └───┬───┘       └──┬───┘
      *              *
      └──────┬───────┘
             -
             │

A Hook or Fork train is capped with a common bus for distributing external arguments to the internal verbs.

In attempting to depict operand flow, a verb is enclosed in a box connected by input and output bars to an adverb, rank specifier, or some other conjunction which has control over both. An adverb application depicts two possible inputs for the modified verb running down into the adverb-labeled "control box". Adverbial processing sends selected portions of those values, in one or more batches, leftward to the verb in its own isolation box. Output is directed rightward to the control box for aggregation and/or reuse, and finally dispatched downward again.

A verb formed with Bond (&) is marked with an R as a reminder that a "third argument" is possible, serving as a repetition "power" or causing a mysterious Domain Error. A verb formed with Compose (also &) is marked with a C to call attention to the second-argument juggling which it performs.

   flowtree '((1: |. 0&{)* (_1: |. 1&{))- ((_1: |. 0&{)* (1: |. 1&{))'
│                                                   │
└┬F─────┬─┬─F─┬─F─────┬─┬─F─┬─F─────┬─┬─F─┬F─────┬─┬┘
 │     ┌┴R┴┐  │      ┌┴R┴┐  │      ┌┴R┴┐  │     ┌┴R┴┐
 │ ┌─┌─┤0  │  │  ┌─┌─┤1  │  │  ┌─┌─┤0  │  │ ┌─┌─┤1  │
 │  { ┌┤└& │  │   { ┌┤└& │  │   { ┌┤└& │  │  { ┌┤└& │
1:  └─┘└─┬─┘ _1:  └─┘└─┬─┘ _1:  └─┘└─┬─┘ 1:  └─┘└─┬─┘
 └───┬───┘    └───┬────┘    └───┬────┘    └───┬───┘
    |.           |.            |.            |.
     └─────┬──────┘             └──────┬──────┘
           *                           *
           └─────────────┬─────────────┘
                         -
                         │

Many conjunctions may be thought of as an adverb, with an additional argument of verb or noun:

  • Rank clearly controls argument delivery and aggregation
  • Bond supplies an "inside" argument not in the "external" input
  • Compose distributes the inputs to its two verbs in a non-standard pattern
  • Agenda chooses which verb gets the inputs

These and some others are therefore diagrammed with one side controlling the other.

Atop and At almost adhere to the pattern of monad/dyad followed by a monad. These conjunctions, however, along with Bond and Compose, are crucial to binding verbs together before arguments are supplied, so they are shown explictly--currently as a leftward sidestep in the downward flow.

   flowtree '(100+ i. 2 4) ((*/@ $@ ]) | 5: * (i.@ $@ [))} i. 3 2 4'

                        2 4
                         │
                    100 i.  3 2 4
                     └─┬─┘    │
                       +     i.
                       └─┐ ┌──┘
           ┌F─┌F─────┌─┐ │ │
           ]  │      [ │ │ │
         ┌@┘  │    ┌@┘ │ │ │
         $    │    $   │ │ │
       ┌@┘    │  ┌@┘   │ │ │
┌─┌─┬┴─┴┐    5: i.     │ │ │
 * ┌┤ / │     └┬─┘     │ │ │
 └─┘└─┬─┘      *       │ │ │
      └───┬────┘       └┬┴─┴┐
          |            ┌┤ } │
          └────────────┘└─┬─┘
                          │

After adaptation to a suitable list of aliases for built-in names, they may also get proper treatment in diagramming.

   flowtree '((SortUp At (Head Rank 1))From Right)Atop ((Nub At (3 Bond From Rank 1))Stitch (3 Bond From Rank 1) (Sum Key) (4 Bond Drop Rank 1))'
                       │                                           │
                       └┬─┬──F──────────────┬─┬──F──────────────┬─┬┘
                        │ │        ┌─┌R┌─┐┌─┴─┴─┐      ┌─┌R┌─┐┌─┴─┴─┐
                        │ │    ┌─┌─┤3    └┤    1│  ┌─┌─┤4    └┤    1│
               ┌─┌R┌─┐┌─┴─┴─┐ From┌┤└Bond┌┤Rank┘│ Drop┌┤└Bond┌┤Rank┘│
           ┌─┌─┤3    └┤    1│   └─┘└───└─┘└──┬──┘   └─┘└───└─┘└──┬──┘
          From┌┤└Bond┌┤Rank┘│                └────────┐ ┌────────┘
            └─┘└───└─┘└──┬──┘                    ┌─┌─┬┴─┴┐
                      ┌At┘                       Sum┌┤Key│
                     Nub                          └─┘└┬──┘
                      └───Stitch──────────────────────┘
                     ┌Atop┘
           └┬─┬──F──┬┘
          ┌─┴─┴─┐   │
      ┌─┌─┤    1│   │
     Head┌┤Rank┘│   │
       └─┘└──┬──┘   │
          ┌At┘      │
       SortUp     Right
          └────┬────┘
             From
               │

Analysis of the (over-wide) diagram produced by this statement with repeated references to some quantities:

   flowtree '(2&{."1) ,"1 (+/"1@ ((2+ spendcodes i. ''aCERPSU'')&{"1)) ,"1 0 1 ((2+ spendcodes i. ''bjl'')&{"1) ,"1 (+/"1@ ((2+ spn+ spendcodes i. ''aCERPSU'')&{"1)) ,"1 0 1 (2+ spn+ spendcodes i. ''bjl'')&{"1'

led to this restructuring:

   flowtree '((2+ spendcodes i."1 ''aCERPSU'',: ''bjl'')&[@]) (((2&{.@ ]) ,"1 ([ ((+/@ ({.@ ])) ,"1 0 1 ({:@ ])) ([ {"1 ])) ,"1 ([ ((+/@ ({.@ ])) ,"1 0 1 ({:@ ])) ((spn&+@ [) {"1 ])))) ]'
                     │                                       │
                     └┬─────────────────F───────────────────┬┘
                      ]                                     │
                    ┌@┘                                     │
    ┌─────────────┴R┴────────────┐                          │
    │             'aCERPSU' 'bjl'│                          │
    │  spendcodes     └───,:──┘  │                          │
    │       └─────┐ ┌─────┘      │                          │
    │            ┌┴─┴┐           │                          │
    │        ┌─┌─┤  1│           │                          │
    │        i. ┌┤ "┘│           │                          │
    │2        └─┘└─┬─┘           │                          │
    │└──────┬──────┘             │                          │
┌─┌─┤       +                    │                          │
 [ ┌┤       └&                   │                          │
 └─┘└────────┬───────────────────┘                          ]
             │                                              │
             └┬F──────────┬F─────┬F┬─F────────┬F─────────┬F┬┘
              │           │      │ │          │          [ │
              │           │      │ │          │        ┌@┘ │
              │           │      │ │          │     ┌┴R┴┐  │
              │           │      │ │          │ ┌─┌─┤spn│  │
              │           │      │ │          │  + ┌┤ └&│  │
              │           │      [ ]          │  └─┘└──┬┘  ]
              │           │      │ │          │        └┐ ┌┘
              │           │     ┌┴─┴┐         │        ┌┴─┴┐
              │           │ ┌─┌─┤  1│         │    ┌─┌─┤  1│
              │           │  { ┌┤ "┘│         │     { ┌┤ "┘│
              │           [  └─┘└─┬─┘         [     └─┘└─┬─┘
              │           └┬F───┬─┘           └──┬F───┬──┘
              │            ]    │                ]    │
              │          ┌@┘    │              ┌@┘    │
              │         {.      │             {.      │
              │        ┌@┘      │            ┌@┘      │
              │ ┌─┌─┬┴─┴┐       ]     ┌─┌─┬┴─┴┐       ]
              │  + ┌┤ / │     ┌@┘      + ┌┤ / │     ┌@┘
              │  └─┘└┬──┘    {:        └─┘└┬──┘    {:
              │      └──┐ ┌───┘            └──┐ ┌───┘
              │       ┌─┴─┴─┐               ┌─┴─┴─┐
              │   ┌─┌─┤1 0 1│           ┌─┌─┤1 0 1│
              │    , ┌┤ "┘  │            , ┌┤ "┘  │
              ]    └─┘└─┬───┘            └─┘└─┬───┘
            ┌@┘         └─────────┐ ┌─────────┘
         ┌┴R┴┐                   ┌┴─┴┐
     ┌─┌─┤2  │               ┌─┌─┤  1│
     {. ┌┤└& │                , ┌┤ "┘│
      └─┘└─┬─┘                └─┘└─┬─┘
           └──────────┐ ┌──────────┘
                     ┌┴─┴┐
                 ┌─┌─┤  1│
                  , ┌┤ "┘│
                  └─┘└─┬─┘
                       │

Alternative format possibilities

   flowtree '1(((3&+)^: 1)&5)"(3- 2+ 1) 1'

Partial box, compact (current)   Full box, compact    Full box, continuous

                    1 1
                    │ │
                   ┌┴─┴──┐
                   │  2 1│
                   │  └┬┘│
                   │3  + │
    ┌┌R┌┐┌┌─┌┐┌┌R┌┐│└┬─┘ │            ┌┌R┌┐┌               ┌┬R┬┐┌┬─┬┐┌
┌─┌─┤3  └┤  1└┤  5└┤ -   │       ┌┌─┌─┤3  └┤          ┌┬─┬─┤3  └┤  1└┤
 + ┌┤└& ┌┤^:┘┌┤ &┘┌┤"┘   │       │ + ┌┤└& ┌┤ . . .    │ + ┌┤└& ┌┤^:┘┌┤ . . .
 └─┘└─└─┘└─└─┘└─└─┘└┬────┘       └─└─┘└─└─┘└          └─┴─┘└─┴─┘└─┴─┘└
                    │

Full box, expanded               Full box, expanded, splits

                     1 1                              1 1
                     │ │                              │ │
                    ┌┴─┴──┐                          ┌┴─┴──┐
                    │  2 1│                          │  2 1│
     ┌┌R┌┐┌┌─┌┐┌┌R┌┐│  └┬┘│           ┌┌R┌┐┌┌─┌┐┌┌R┌┐│  └┬┘│
┌┌─┌┐│   ││   ││   ││3  + │      ┌┌─┌┐│└┬┘││└┬┘││└┬┘││3  + │
│   └┤3  └┤  1└┤  5└┤└┬─┘ │      │└┬┘└┤3  └┤  1└┤  5└┤└┬─┘ │
│ + ┌┤└& ┌┤^:┘┌┤ &┘┌┤ -   │      │ + ┌┤└& ┌┤^:┘┌┤ &┘┌┤ -   │
│   ││   ││   ││   ││"┘   │      │ │ ││ │ ││ │ ││ │ ││"┘   │
└─└─┘└─└─┘└─└─┘└─└─┘└┬────┘      └─└─┘└─└─┘└─└─┘└─└─┘└┬────┘
                     │                                │

   flowtree '(((0= ,) #)@ ((0= ,) # (,@ ({@ (,@ (,@ (< i."0))&$)))))'
      Side feeds                 versus  Top feeds
     │                         │        │                   │
     └┬─┬F──────┬─────────────┬┘        └┬F───┬────────────┬┘
      │ |       │           C $          │    │            $
      │ |       └┐         H┌&┘          │    │         C┌&┘
      │ │        |    └┬───┐|            │    └┐       H┌┘
      │ │        |┌──┌─┤  0│┘            │     │     ┌┴─┴┐
      │ │        |└i.┘┌┤ "┘│             │     │ ┌─┌─┤  0│
      │ │        |  └─┘└─┬─┘             │     │ i. ┌┤ "┘│
      | │        └───<───┘               │     │  └─┘└─┬─┘
      │ |         ,─@┘                   │     └───┬───┘
      │ |      ,─@┘                      │         <
   0  └,┘   {─@┘                         │       ┌@┘
   └─=─┘ ,─@┘                            │       ,
     └─#─┘                               │     ┌@┘
   ┌H┌@┘          └───<───┘              │     ,
   │ #                |        |         │   ┌@┘
0  └,┘             ,─@┘      ,─@       0 ,   {
└─=─┘     or       |    or   |         └┬┘ ┌@┘
  │             ,─@┘       ,─@          =  ,
                |          |            └┬─┘
            {─@┘         {─@             #
   |   |    |    |   |   |             ┌@┘
   └─=─┘ ,─@┘    └─=─┘ ,─@          ┌H┌┘
     |   |         |   |            │ #
     └─#─┘         └─#─┘            └┬┘
       |             |             0 ,
   ┌H┌@┘                           └┬┘
   │ #                              =
   | |                              │
   └,┘
0   │
└─=─┘
  │

Comments

These syntactic diagrams give no depiction of the type, amount, or structure of the data which may be processed. They do not obviate the need to understand the meanings of each symbol or named object, especially the argument-delivery actions of adverbs and conjunctions. What it can help with is understanding whether a verb's monadic or dyadic meaning is being called for, and where its argument(s) is(are) coming from. Once a likely flow structure has been designed, then a trace report can show what results are actually created at each "station" in the pipe network.

This version is published for public comment on the usefulness of this type of statement analysis and the particular design choices made here. I intend to do more testing and code cleanup. If you are moved to comment on this work, please take some time to collect and organize your thoughts before offering them for my use. I invite:

  • Comments on structural details
  • Comments on format options
  • Tests of a variety of statements
  • Reports of problematic depictions
  • Offers of alternative actions
  • Code for specific changes