2D Diagram Editing

Here’s a first crack at a summary of the “atoms” for diagram editing.  Basically a hand-edited list of commands from the menu of the tool, arranged in left-to-right order.  The interesting (weird) stuff is further down (lines, nodes, selection, phantom, etc).  Don’t be surprised if you need to ask for elaboration (I barely recognize some of this stuff) :-).

All drawing command atoms were on the menu. Clearly, drawing a diagram through a drop-down menu is the worst possible UX, but the menu was good for reminding one of available commands, esp. the ones used most infrequently, a la emacs.

Forcing ourselves to put *every* atomic command on the menu was a design cross-check, “did we find all of the atoms, are the atoms atomic enough?”.

The atoms were bound to keys, gestures and mouse actions via a startup dot-file.  In emacs fashion this was implemented in CL, one could create scripts using atomic actions and bind those scripts to keys, gestures and mouse actions.

At this point, after building many not-so-good diagram editors, we began to realize that we simply needed to draw free-form diagrams and remove any “semantics checking” from the editor – the editor didn’t know anything about the base data structures (e.g. components, ports, flows) that we wanted to deal with in the end.

The menu summarized, here, contains some recognizable shapes, but these were “scripts” (palettes of pre-constructed handy shapes) built up from atoms, read in from a dot-file file at startup.  We used the tool to construct these shapes, then saved them into the dot-file).  Any actual coordinates contained in the dot-file were “relative” to the origin of each of the diagram scripts.  (I’ll add to the confusion by posting a factbase of a sample component in another post).

The editor produced a “fact base” (aka prolog-like assertions, aka design recovery) of points, lines, text, etc.

The fact base would be passed through a series of prolog-like inferencing rules to parse and build up semantic information.  (Again, see https://github.com/guitarvydas/vsh/tree/master/cl-vsh for the simplest variation on this theme that I’ve been able to come up with).

Point and mark were renamed to cursor and mark.

Nodes (iirc) are actual points on a shape (i.e. endpoints of lines).

Controls were points that were used to control the shape of curves (the tool was also used to build state diagrams).

Note that there are atomic commands for controlling rubber-banding, phantoms (the “ghost” images displayed when rubber-banding, moving, etc), selection, movement, hit-testing, grouping, etc.

Since the diagram editor was not allowed to understand the notion of “objects”, hit-testing was done at an atomic level – a node or a line.  When you hovered the cursor (via keyboard or mouse) over a set of atomic objects, the editor would display a gray highlight over the “top”, to-be-selected, atom (iirc, this idea comes from “The Humane Interface”, J. Raskin).  If you performed the “select” command, the “top” atom would become selected.  In the – likely – case that many atoms intersected at one point on the screen (e.g. a node, an end-point of a line, an end-point of another line, etc), you could scroll through the atoms by using the roll-hits command(s), making each successive atom the “top” one (aka “to-be-selected”).

You can see that there exists a plethora of “select” commands for the various cases of interest, e.g. select all atoms underneath the cursor, select only the “top” atom, select all atoms and their relatives (e.g. every line underneath the cursor along with every node intersecting with those lines, etc), select all atoms contained within the “group” underneath the cursor and so on.

Movement was related to selection.  If you wanted to move a “component” – drawn as four lines – you could select each node (endpoint) separately (very tedious) and then move the whole selection, or, you could select a node and all of its relatives, or, you could “group” the atoms making up the component and select the group, and so on.

[Early versions of “undo” produced rather humourous results.  E.G. a move of all of the atoms making up a component would be recorded as a separate move of each atom.  Multiple undo’s were required to restore the component to its original position – undo the move to the top-left node, undo the move to the top-right node, and so on.]

[credit: much of the atomization work was performed by John Shuve.]

I’d be glad to discuss and explain further.  I’ll just bs if I can’t actually remember nor lookup in code.

pt

help-menu
“Help”
“VF Reference”
“About Visual Frameworks…”

new-window-menu
“New Window”
“Component Editor”
“Text Editor”
“Instance Tree”
“Component Palette”
“Application Variant”

window-menu
“Windows”
“Next Window”
“Previous Window”
“Duplicate Window”
new-window-menu
“[window list]”

menu-11

buffers-menu
“Buffers”
“Next in History”
“Previous in History”
“History”
“[buffer list]”

“Close”
buffer-close
“Other”
other-buffer
menu-return-buffer-list
buffer-select

build-menu
“Build”
“Compile”
“Compile All”
“Download…”

resize-menu
“Resize”
“Expand W”
“Shrink W”
“Expand N”
“Shrink N”
“Expand E”
“Shrink E”
“Expand S”
“Shrink S”

set-resize-menu
“Set Resizing”
“Left…”
“Top…”
“Right…”
“Bottom…”

groups
“Groups”
“Group Selected”     group-selected-objects
“Ungroup Selected”     ungroup-selected-objects
resize-menu
set-resize-menu

text
“Text”
“Create Text”   new-text-block
“Create Hyperlink”   new-hyperlink-icon
“Create Code”   new-code-icon
“Edit In-Place”   unimplemented
“Edit In Recent Text Editor”   edit-text-at-cursor-in-MRU-

editor
“Edit In New Text Editor”   edit-text-at-cursor-in-new-editor
“Associate as Comment”
“Follow Link”
“Follow Link In Recent Window”
“Follow Link In This Window”
“Follow Link In New Window”
“Single Line” text-single-line
“Multi-Line” text-multi-line

text-size-menu
text-font-menu
text-style-menu
text-justification-menu
text-anchor-menu
text-pad-menu
text-fore-color-menu
text-back-color-menu
text-lock-menu

text-pad-menu “Pad For Anchor”
“Left…”     text-pad-left
“Top…”     text-pad-top
“Right…”     text-pad-right
“Bottom…”     text-pad-bottom

text-lock-menu “Lock Text”
“Lock”     text-lock
“Unlock”     text-unlock

text-fore-color-menu
“Text Color”
“Black”     text-fore-color-black
“White”     text-fore-color-white
“% Red…”     text-fore-color-p-red
“% Green…”     text-fore-color-p-green
“% Blue…”     text-fore-color-p-blue

text-back-color-menu
“Background Color”
“Transparent”     text-back-color-transparent
“White”     text-back-color-white
“Black”     text-back-color-black
“% Red…”     text-back-color-p-red
“% Green…”     text-back-color-p-green
“% Blue…”     text-back-color-p-blue

text-size-menu
“Size”

“8pt”     text-size-8pt
“10pt”     text-size-10pt
“12pt”     text-size-12pt
“14pt”     text-size-14pt
“18pt”     text-size-18pt
“24pt”     text-size-24pt
“36pt”     text-size-36pt
“48pt”     text-size-48pt
“72pt”     text-size-72pt
“Other…”     text-size-other

text-font-menu
“Font”
“Helvetica”   text-font-helvetica
“Times”   text-font-times
“Courier”   text-font-courier

text-style-menu
“Styles”
“Bold”   text-style-bold
“Not Bold”   text-style-not-bold
“Italic”   text-style-italic
“Not Italic”   text-style-not-italic

text-justification-menu
“Justification”
“Left”   text-justification-left
“Center”   text-justification-center
“Right”   text-justification-right

text-anchor-menu
“Anchor”
“Center”   text-anchor-center
“W”   text-anchor-w
“NW”   text-anchor-nw
“N”   text-anchor-n
“NE”   text-anchor-ne
“E”   text-anchor-e
“SE”   text-anchor-se
“S”   text-anchor-s
“SW”   text-anchor-sw
“W Base”   text-anchor-w-base
“Center Base”   text-anchor-center-base
“E Base”   text-anchor-e-base

lines
“Lines”
“New Line Mark to Cursor”     new-line-segment
“Extend Line Mark to Cursor”     extend-line-segment
“Split”     line-split
“Merge”     unimplemented
“Merge Collinear Segements”
“New Ellipse Mark To Cursor”     new-ellipse

line-width-menu
line-pattern-menu
line-shape-menu
line-arrow-menu
line-fore-color-menu
line-back-color-menu

line-fore-color-menu
“Line Color”
“Black”     line-fore-color-black
“White”     line-fore-color-white
“% Red…”     line-fore-color-p-red
“% Green…”     line-fore-color-p-green
“% Blue…”     line-fore-color-p-blue

line-back-color-menu
“Fill Color”
“Transparent”     line-back-color-transparent
“White”     line-back-color-white
“Black”     line-back-color-black
“% Red…”     line-back-color-p-red
“% Green…”     line-back-color-p-green
“% Blue…”     line-back-color-p-blue

line-width-menu
“Width”
“Hairline”     line-width-hairline
“1pt”     line-width-1pt
“2pt”     line-width-2pt
“3pt”     line-width-3pt
“4pt”     line-width-4pt
“6pt”     line-width-6pt
“8pt”     line-width-8pt
“10pt”     line-width-10pt
“Other…”     line-width-other

line-pattern-menu
“Style”
“Solid”     line-pattern-solid
“Dashed”     line-pattern-dashed
“Dotted”     line-pattern-dotted
“Mitered Joints”     line-style-mitered-joints
“Rounded Joints”     line-style-rounded-joints

line-shape-menu
“Shape”
“Straight”   line-shape-straight
“Curved”   line-shape-curved
“Rounded”   line-shape-rounded
“Line”     line-shape-not-polygon
“Polygon”     line-shape-polygon

line-arrow-menu
“Arrows”
“Start Arrow”   line-arrow-initial
“No Start Arrow”   line-arrow-not-initial
“End Arrow”   line-arrow-final
“No End Arrow”   line-arrow-not-final

nodes
“Nodes and Control Points”
“Add At Cursor”     add-control-at-cursor
“Delete Selected”     delete-selected-nodes-and-controls
“Add Dot To Selected”     add-dot-to-selected-nodes
“Delete Selected Dots”     delete-dots-from-selected-nodes
“Show at      show-nodes-or-controls-at-cursor
“Show in Region”     show-nodes-or-controls-in-region
“Show All”     show-all-nodes-or-controls
“Hide at Cursor”     hide-nodes-or-controls-at-cursor
“Hide in Region”     hide-nodes-or-controls-in-region
“Hide All”     hide-all-nodes-or-controls

state-shapes
“State Diagram Shapes”
“Simple State”     state-create-simple-state-at-cursor
“Container State”
“Selector”
“Entry Point”
“Terminal”

schematic-shapes
“Schematic Diagram Shapes”
“Input Port – Left”
“Input Port – Right”
“Output Port – Left”
“Output Port – Right”
“Named Net Source”
“Input Pin – Left”
“Input Pin – Right”
“Output Pin – Left”
“Output Pin – Right”
“Standard Pinless Component”

“Component Outline Shapes”
“Input Pin – Left”
“Input Pin – Right”
“Output Pin – Left”
“Output Pin – Right”
“Standard Pinless Component”
other-templates “Other Shapes”

objects-menu
“Objects”
outline-shapes
schematic-shapes
state-shapes
other-templates
“Import Component…”
“Export Component…”
“Export Component Using Defaults”
“Synchronize Components”
“Reload From File”
“Overwrite File”
“Check Against File”
“Reload Selection”
“Reload All”

properties-menu
“Properties”
“Set Name…”     properties-set-name
“Set Type…”     properties-set-type

global-properties-menu
“Global Properties”
“Set Name…”     global-properties-set-name
“Set Type…”     global-properties-set-type

move-menu
“Move Selection” move-phantom-menu
“By Mark To Cursor”     move-selection-by-m2c
“By Cursor To Mark”     move-selection-by-c2m
“To Phantom”     move-selection-to-phantom
“Page Up”
“Page Down”
“Page Left”
“Page Right”
“Grid Up”
“Grid Down”
“Grid Left”
“Grid Right”
“Up”
“Down”
“Left”
“Right”

move-selection-cursor-menu
“Anchor To Cursor”
“Origin”
“Center”
“NW”
“N”
“NE”
“E”
“SE”
“S”
“SW”
“W”

move-selection-mark-menu
“Anchor To Mark”
“Origin”
“Center”
“NW”
“N”
“NE”
“E”
“SE”
“S”
“SW”
“W”

move-selection-drawing-menu
“Origin To Drawing”
“Center”
“NW”
“N”
“NE”
“E”
“SE”
“S”
“SW”
“W”

move-selection-viewport-menu
“Origin To Viewport”
“Center”
“NW”
“N”
“NE”
“E”
“SE”
“S”
“SW”
“W”

move-phantom-menu
“Move Phantom”
“Reset Phantom”     move-phantom-to-selection
“By Mark To Cursor”     move-phantom-by-m2c
“By Cursor To Mark”     move-phantom-by-c2m
“Page Up”
“Page Down”
“Page Left”
“Page Right”
“Grid Up”
“Grid Down”
“Grid Left”
“Grid Right”
“Up”
“Down”
“Left”
“Right”

move-phantom-cursor-menu
“Anchor To Cursor”
“Origin”
“Center”
“NW”
“N”
“NE”
“E”
“SE”
“S”
“SW”
“W”

move-phantom-mark-menu
“Anchor To Mark”
“Origin”
“Center”
“NW”
“N”
“NE”
“E”
“SE”
“S”
“SW”
“W”

move-phantom-drawing-menu
“Origin To Drawing”
“Center”
“NW”
“N”
“NE”
“E”
“SE”
“S”
“SW”
“W”

move-phantom-viewport-menu
“Origin To Viewport”
“Center”
“NW”
“N”
“NE”
“E”
“SE”
“S”
“SW”
“W”

zoom-menu
“Zoom”
“Zoom In”
zoom-in
“Zoom Out”
zoom-out
“Zoom 1:1”
zoom-one-to-one
“Zoom All”
zoom-all
“Zoom to Region”
zoom-region

pan-menu
“Pan”
“Center on Cursor”   pan-center-on-cursor
“Page Up”     pan-page-up
“Page Down”     pan-page-down
“Page Left”     pan-page-left
“Page Right”     pan-page-right
“Up”     pan-up
“Down”     pan-down
“Left”     pan-left
“Right”     pan-right

pan-to-drawing-menu
“Pan To Drawing”
“Center”   pan-to-center
“NW”   pan-to-nw
“N”   pan-to-n
“NE”   pan-to-ne
“E”   pan-to-e
“SE”   pan-to-se
“S”   pan-to-s
“SW”   pan-to-sw
“W”   pan-to-w

pan-to-viewport-menu
“Pan To Viewport”
“Center”   pan-to-center
“NW”   pan-to-nw
“N”   pan-to-n
“NE”   pan-to-ne
“E”   pan-to-e
“SE”   pan-to-se
“S”   pan-to-s
“SW”   pan-to-sw
“W”   pan-to-w

selection-menu
“Select”
“Select All At Cursor”
select-all-objects-at-cursor-and-maintain-connections
“Select All At Cursor And Break”
select-all-objects-at-cursor-and-ignore-connections
“Select Current At Cursor”
select-current-object-at-cursor-and-maintain-connections
“Select Current At Cursor And Break”
select-current-object-at-cursor-and-ignore-connections
“Select In Region”
select-objects-in-region
“Select All”
select-all
“Deselect All At Cursor”
deselect-all-objects-at-cursor-and-maintain-connections
“Deselect All At Cursor And Break”
deselect-all-objects-at-cursor-and-ignore-connections
“Deselect Current At Cursor”
deselect-current-object-at-cursor-and-maintain-connections
“Deselect Current At Cursor And Break”
deselect-current-object-at-cursor-and-ignore-connections
“Deselect In Region”
select-objects-in-region
“Deselect All”
deselect-all
“Set Selection Origin At Cursor”
set-selection-origin-at-cursor
“Clear Selection Origin”
clear-selection-origin

“Push Selection”
push-selection
“Pop Selection”
pop-selection
“Roll Selection Forward”
roll-selection-forward
“Roll Selection Backward”
roll-selection-backward

“Whole Wire Selection”
:selected nil
“Intersecting Marquee”
inclusive-marquee-select
:retract-callback ‘menu-inclusive-marquee-retract
:selected t

“Visible Selection”
visible-selection-select
:retract-callback ‘menu-visible-selection-retract
:selected t

:popup-callback ‘menu-indicate-wholewire-intersectingmarquee-visibleselection
:interaction :multiple-selection

cursor-menu
“Cursor”
“Set Mark At Cursor”
set-mark-at-cursor
“Set Cursor At Mark”
set-cursor-at-mark
“Exchange Cursor And Mark”
exchange-cursor-and-mark

“Roll Hits Forward”
next-in-hit-stack
“Roll Hits Backward”
previous-in-hit-stack

“Push Mark”
push-mark
“Pop Mark”
pop-mark
“Roll Mark Forward”
roll-mark-forward
“Roll Mark Backward”
roll-mark-backward

cursor-move-menu
“Move Cursor”
“Page Up”     cursor-page-up
“Page Down”     cursor-page-down
“Page Left”     cursor-page-left
“Page Right”     cursor-page-right
“Grid Up”     cursor-up
“Grid Down”     cursor-down
“Grid Left”     cursor-left
“Grid Right”     cursor-right

“Up”     cursor-up
“Down”     cursor-down
“Left”     cursor-left
“Right”     cursor-right

cursor-move-to-drawing-menu
cursor-move-to-viewport-menu
cursor-move-to-drawing-menu
“Move To Drawing”
“Center”   move-cursor-to-drawing-center
“NW”   move-cursor-to-drawing-nw
“N”   move-cursor-to-drawing-n
“NE”   move-cursor-to-drawing-ne
“E”   move-cursor-to-drawing-e
“SE”   move-cursor-to-drawing-se
“S”   move-cursor-to-drawing-s
“SW”   move-cursor-to-drawing-sw
“W”   move-cursor-to-drawing-w

cursor-move-to-viewport-menu
“Move To Viewport”
“Center”   move-cursor-to-viewport-center
“NW”   move-cursor-to-viewport-nw
“N”   move-cursor-to-viewport-n
“NE”   move-cursor-to-viewport-ne
“E”   move-cursor-to-viewport-e
“SE”   move-cursor-to-viewport-se
“S”   move-cursor-to-viewport-s
“SW”   move-cursor-to-viewport-sw
“W”   move-cursor-to-viewport-w

mark-move-menu
“Move Mark”
“Page      mark-page-up
“Page Down”     mark-page-down
“Page Left”     mark-page-left
“Page Right”     mark-page-right

“Grid Up”     mark-up
“Grid Down”     mark-down
“Grid Left”     mark-left
“Grid Right”     mark-right

“Up”     mark-up
“Down”     mark-down
“Left”     mark-left
“Right”     mark-right

mark-move-to-drawing-menu
“Move To Drawing”
“Center”   move-mark-to-drawing-center
“NW”   move-mark-to-drawing-nw
“N”   move-mark-to-drawing-n
“NE”   move-mark-to-drawing-ne
“E”   move-mark-to-drawing-e
“SE”   move-mark-to-drawing-se
“S”   move-mark-to-drawing-s
“SW”   move-mark-to-drawing-sw
“W”   move-mark-to-drawing-w

mark-move-to-viewport-menu
“Move To Viewport”
“Center”   move-mark-to-viewport-center
“NW”   move-mark-to-viewport-nw
“N”   move-mark-to-viewport-n
“NE”   move-mark-to-viewport-ne
“E”   move-mark-to-viewport-e
“SE”   move-mark-to-viewport-se
“S”   move-mark-to-viewport-s
“SW”   move-mark-to-viewport-sw
“W”   move-mark-to-viewport-w

show-layer-menu
“Show Layers”
“Base”
“Pin Types”
“[more layers]”

active-layer-menu
“Active Layer”
“Base”
“Pin Types”
“[more layers]”

view-sheet
“View Sheet”
:items-function ‘menu-return-sheet-list
:popup-callback ‘menu-indicate-current-sheet-in-sheet-list
sheet-list-select
:retract-callback ‘menu-sheet-list-retract
:interaction :single-selection

view-menu
“View”
:component
view-sheet
“New Sheet”     create-new-sheet
“Rename Current Sheet”     edit-sheet-name
“Destroy Current Sheet”     destroy-current-sheet

active-layer-menu
show-layer-menu    “New Layer”
“Layer Properties”
“Destroy Layer”

“Instance Tree”

“Rubber Band”
rubber-band-select
:retract-callback ‘menu-rubber-band-retract
“Marquee”
marquee-select
:retract-callback ‘menu-marquee-retract
“Active Mouse UI”
active-mouse-select
:retract-callback ‘menu-active-mouse-retract
:popup-callback ‘menu-indicate-rubberband-marquee-activemouse

replace-menu
“Replace”
“Text…”
“Buffer…”
“Buffer Deeply…”
“All Buffers…”
“Project…”

search-menu
“Search”
“Incremental…”
“Text…”
“Buffer…”
“Buffer Deeply…”
“All Buffers…”
“Project…”

edit-menu
“Edit”
“Undo”
edit-undo
“Redo”
edit-redo
“Cut”     edit-cut
“Copy”     edit-copy
“Paste”     edit-paste
“Delete”     edit-delete

“Select All”     select-all
“Deselect All”     deselect-all

“Set Clipboard Origin At Cursor”     set-clipboard-origin-at-cursor
“Clear Clipboard Origin”     clear-clipboard-origin

“Schematic Mode” schematic-mode
“State Machine Mode” state-machine-mode
“Code Part Mode” code-part-mode
“DWG Mode” drawing-mode
“Base Mode” base-mode

“Re-Paste Forward”
“Re-Paste Backward”
“Roll Clipboard Forward”
“Roll Clipboard Backward”

“Next Item”
“Previous Item”
search-menu
replace-menu

text-mru-menu
“Recent Text Files”
“[MRU file list]”

workspace-mru-menu
“Recent Workspace Files”
“[MRU file list]”

variant-mru-menu
“Recent Variant Files”
“[MRU file list]”

project-mru-menu
“Recent Project Files”
“[MRU file list]”

palette-mru-menu
“Recent Palette Files”
“[MRU file list]”

graphics-mru-menu
“Recent Graphic Files”
“[MRU file list]”

component-mru-menu
“Recent Component Files”
“[MRU file list]”

open-item-menu-1
“Open Buffer”
“Component Outline…”
open-component-outline
“Component Implementation…”
open-component-implementation
“Graphics Only…”
open-graphics-only

new-item-menu-1
“New Buffer”
“Outline Only”
new-component-outline
“Schematic Diagram”
“State Diagram”
“Variant Socket”
“Graphics Only”
new-graphics-only

file-menu
“File”
new-item-menu-1
open-item-menu-1
“Save Buffer” save-buffer
“Save Buffer As …” save-buffer-as
“Import VF Template…”
import-template
“Import VF File…”
“Print” print

Something Similar

This article describes some of the basic principles:

Click to access Samek0607.pdf

http://www.state-machine.com/index.html

Recipe: Concurrent (bm)FBP components in a single thread.

Write a class (if you insist on using classes) for a Part (aka Component).

It has:

• A set of input pins, each with some kind of ID.  In Lisp, I use a symbol.  In C I use an integer, unique within the part, or a pointer into a hash table of strings.
• A set of output pins, each with some kind of ID.
• An input queue.
• An output queue.
• A busy flag.  Set when running, so that feedback messages don’t cause recursion.

Subclass this twice.

1. Leaf (code) part.  It adds a “handler” to the above – the code block with a switch statement in it.
2. Schematic part – a hierarchical part (aka sub-net).  It adds to the above:
   • a collection of part instances
   • a set of nets specifying which outputs connect to which inputs ; these are going to be tuples {part_ident, pin_ident}
   • N.B. you need to differentiate between “self” and the children parts.  In C, I use -1 as the ID for self.  In lisp, I use some goofy symbol like %self%.  IP’s coming in on the input pins of the schematic are tagged with %self%.  IP’s being sent to the output pins of the schematic are tagged with %self%.  Visually, when you’re looking at the innards of a schematic part, you see an FBP diagram, with a bunch of inputs (on the left in my mind) coming from the outside world and a bunch of outputs (on the right) going to the outside world.

Now create a class for Events (IPs).  It contains a slot for pin_ID and a slot for a reference to the data.  In C, I overload the data slot.  In compiler terminology there is a difference between “scalars” (things which are small enough to directly fit into a pointer, e.g. 4 bytes) and “non-scalars” things which are aggregates and sit in the heap having their reference fit into the data slot (lists, arrays, etc).  Clearly the class needs a bit that says how to use the data slot – is it a scalar or a reference to a non-scalar.  Or you can use sub-classing,  I guess.

That’s it for components and IP’s.  We’re well past the half-way point!

You need a Ready queue for components, FIFO is good (LIFO is good, too).  Depending on your garbage collector, you might also want another not_Ready queue.

The scheduler is stupid-simple.  It pulls any component off of the Ready queue, sets its BUSY bit to TRUE and then (1) if it’s a leaf part, calls its handler, (2) if it’s a schematic part, calls the schematic handler (with the schematic as “self”).  When the part “returns”, set the BUSY bit to FALSE and grab something else off the Ready queue.  Rinse and repeat.

The schematic handler is just a bit of code that runs any and every child part contained within it.  It’s a recursive scheduler.  The schematic stays BUSY=TRUE until all of its children become BUSY=FALSE.  I.E. a part runs to completion.  In a leaf part that means that it “returns”.  In a schematic part that means that none of its children are busy.

When a child part finishes, the schematic handler looks at the child’s output queue and, if anything is on it, it grabs the output pin (in the IP) and looks up the net in its own set of nets.  It then rewrites the pin to be the input pin of the receiving part and pushes the re-jigged IP onto the input of the receiving part.  If fan-out is allowed, the IP is copied N times before re-jigging and pushing.  [And here is the problem with fan-out – do we deep-copy the data or allow it to be shared?  In C, the answer is almost always – share it, for efficiency.  There are other answers].

A part that is BUSY=TRUE is not considered to be READY (it is RUNNING).

That’s it.

This is shu-ha-ri.  The way I’ve always done it.  Learn this way, then you will be able to see other ways.

I backed into doing it this way (from thinking about it as EE) and have been continuously trying to clean it up and simplify it.

There are, obviously, other ways.  No need for input queues on parts.  Just a system-wide queue containing all of the IP’s waiting to be delivered, suitably tagged by tuples {part_REF, pin, data}.  Similarly, only one system-wide output queue could be used.  Only the RUNNING part is generating output, so why waste space by granting output queues to the non-RUNNING parts?  Maybe the BUSY bit is not required (esp. if the part defers all of its output – I guess it cannot recur (an earlier variant a decade or two ago was written such that it could recur – bad choice!)).

ps.  Multi-core / distributed is a no-brainer from this perspective.  One needs a semaphore or test-and-set to throw stuff over the wall to another core, and then it’s just the same.  Don’t worry about this for now.  Wrap your mind around the simplicity of the above.  When you understand it, the rest will follow.

pps.  A runtime for FBP (classic) can be derived in the same way as above.  Some of the semantics change slightly, and extra queues are needed to implement back-pressure.  See https://github.com/guitarvydas/collate-fbp-classic for hints at how to accomplish this.

Apache NiFi and FBP

https://www.youtube.com/watch?v=sQCgtCoZyFQ

See description of NiFi starting around 14:00

Around 29:00, he “taps” a production system, without affecting production, and sends live data to the lab.

Long Running Loops

Q:  What makes a “process” expensive?

A:  Implicit support for long-running loops (LRL).

Long-running loops come in two forms:

1. Obvious loops.

2. Non-obvious “loops” – hidden, deep chains of control flow that take a long time to resolve (e.g. “return”), libraries calling libraries.

Long-running loops are not intrinsically inefficient.  The problems caused by long-running loops (LRL’s) are the epicycles that have been added to operating systems to *implicitly* support LRL’s.

The Problem

As computing evolved from batch processing (LRL’s to cycle through files of records or to perform mathematical computation) towards interactive shared multi-user mode, the obvious questions were not asked, i.e. how to change the *languages* to accommodate the new style of usage of CPU’s.

Most applications built with “standard” languages are built as (hidden) LRL’s.

The Accepted Solution

Instead, the languages were not altered and the operating systems were changed to support “full preemption”.

In this model, the operating system can interrupt any application at any time and save *all* of its state and start up another app.

[Even so-called “stateless” languages have state, managed implicitly by the O/S.]

What is the state variable(s) for such apps?  It’s called a “stack”.

In this model, every app needs to have its own state variable (stack).

Since we don’t know ahead of time how big to make the state variable (stack),  yet another epicycle needed to be added.

The operating system needed to be embellished to detect stack overflows and to grow the size of the state variable (stack) if it became too large.

This, done in software (the operating system) was too inefficient, so this epicycle was moved into hardware – leading up to the invention of the MMU.

Another Solution

What seemed to be ignored was that other solutions were possible.

One such solution would be to create language constructs that disallowed LRL’s.  State machines fall into this category.

Another would be to create compilers that emitted code that would cooperate with the operating system – telling the system at what points in execution it would be convenient to suspend a given process.

Note that an application built using only Call/Return constructs, i.e. any state-of-the-art language (procedural, functional, OO, etc), tends to defy such treatment.

Callback Hell

What is needed is a set of subroutines that perform some operations, then return to the “top level” (thus, obviating the need for saving the stack).

This is, in essence, what node.js (libevent, etc) does, but in a manner that makes it hard to program.

Imagine how Excel (just to pick an app at random) operates.  Excel performs a calculation relatively rarely – most of the time, it is waiting for user input – mouse, keyboard, etc.  When Excel is waiting for input, it does not really need to have its stack saved, and, when it is performing a calculation it seems wasteful to preempt it – let it finish the calculation, then return to waiting for input.

Excel is programmed using a “Windows loop” (I assume).  This is wasteful – it demands that a stack be used, when, in fact the stack normally contains “nothing” – a small amount of state that points to the “Windows loop” re-entry point.  This state could be saved in a small state variable – a stack is not required.

If Excel were programmed in a node.js manner, a vector of callbacks, the stack could be eliminated.

Node.js callbacks are notorious for being hard to program / debug.

Multiple Cores and Distributed Programming

One will note that programming multiple cores and, worse, programming distributed systems would be easier if “everything was a callback”.

Languages based on the Call/Return paradigm (procedural, functional, OO, etc) do not lend themselves to solving multiple core and distributed programming.

The call/return stack causes strong coupling between routines that hinders this kind of programming.

Fixing Callback Hell

Callback hell does not occur because callbacks are hard to program / debug, but is due to the fact that the underlying programming language(s) is not designed to conveniently deal with callbacks in a structured and modular manner.

What is needed is a language (or a system of macros) that groups callbacks together in modular hierarchies.

When “everything is a callback”, calling another routine consists of “sending a message” to the routine.

Existing Solutions to Callback Hell

At least two languages already exist that exhibit the required semantics:

1. StateCharts (Harel) (hierarchical state machines)

2. Flow-Based Programming (Morrison) (“BASH pipe syntax” on steroids).

Actors, CSP, Erlang come close, too.

It appears that none of the authors of these languages has realized that their languages could be used to annihilate the dogmatic notion of multiple “stacks”.

Processes

Callback hell is also solved by making everything a process.  Every subroutine is a process.  Every library routine is a process.  Routines communicate by simply sending messages to other routines wrapped in processes, instead of calling the routines directly (and waiting for a synchronous return).

A process can be lightweight and need no stack, if it simply finishes what it is doing quickly and then “returns” to the scheduler.

A LRL (long-running-loop) is treated explicitly by having a process send “do another loop” messages to itself (then returning to the scheduler).  Or by adding some syntactic sugar that accomplishes the same thing.

In this model, general recursion needs to be disallowed, also, but tail recursion could work via messages as above.

FBP

FBP (flow-based programming) appears to use processes and stacks, but, it uses so few of the features of a standard O/S, that it is possible, and simple, to write an FBP scheduler as described above.

What About Protected Memory Spaces?

As soon as the paradigm of processes is mentioned, the dogmatic knives come out.

Let us compare apples with apples and oranges with oranges.

What is discussed in the above paragraphs is a programming language that feels like building software with processes.

What is not implied, in the above, is the notion of memory space protection.

When one creates a program using subroutines (procedural, functional, OO, etc) and one inadvertently inserts a bug into the program, one expects incorrect behaviour and possible crashing.

Likewise, when one creates a program using the above asynchronous “processes” (callbacks, etc), one should expect incorrect behaviour and crashing if the program contains a bug.

What is discussed above is not the same as an operating system “process”.

The current dogma assumes that the word “process” implies memory management and protection.

To compare this dogma, correctly, with currently existing state-of-the-art languages would require that every subroutine sit in its own address space, handled by the MMU.  For example the function HelloWorld() would have its own address space.  The HelloWorld() function calls printf().  Printf() sits in its own address space and causes an MMU mapping on the call and a re-mapping on the return.

Faking Asynchronous I/O

Asynchronous I/O

1. Bare Metal

The best way to do asynchronous I/O with FBP, is to throw away the O/S and run off of hardware interrupts.  When a hardware input fires, it wakes up the kernel and lets it run until the all of the components that handle the input have run to completion.

This requires the use of a (lockable) queue.  Let’s say that two keypresses come in rapid succession, each triggering a hardware interrupt.

The first keypress interrupt wakes the kernel and hands control, i.e. the cpu, to the kernel.  The kernel grabs the keypress and re-enables interrupts.  Then the kernel creates an IP (a small data structure) for the keypress and runs the FBP system.

If the second keypress interrupt occurs before the kernel has returned to an idle state, then that keypress must simply be placed on the I/O queue and the 2nd interrupt ends (re-enable interrupts then RTI (return from interrupt)).

2. Inside an O/S (green thread)

2.1 Event Loop / Windows Loop

The O/S wraps the main-loop of an app inside an (expensive) process.  Your code – the FBP kernel plus components simply run inside the main-loop.  In this model, the O/S already queues up events (e.g. mouse events, etc.) and metes them out one at a time, calling the main-loop for each event.

Time-slicing and other expensive behaviours are supplied by the O/S as a “courtesy”.

The question arises – why bother with an FBP kernel in this case, why not just use a deep stack of calls, as was originally intended by the O/S developers?

Answer: FBP is a paradigm for designing and testing Software Architectures.  Designing an app as a set of (apparently) asynchronous FBP components makes everything easier.  Additionally, it makes it possible to draw sensible diagrams of the app’s architecture and to compile those diagrams to code.

Another way to think about FBP is that an FBP component is a DLL with all of its input API and output API linked at load time.  A component must call other components via the link-loader’s table.  This analogy can give a sense of the degree of decoupling (architecturally good) that FBP provides.  The analogy is still flawed, because FBP removes the target’s name from the tables – the component cannot know which components (if any) are connected to its output tables.

2.2 Asynchronous Callbacks

This is what node.js does.  You call node.js and ask it to perform some I/O.  You give it a pointer to the callback routine which will be fired when the I/O has done its thing.

Everybody knows that programming with callbacks is rife with danger – all sorts of hidden interactions come into play.

FBP makes this paradigm plausible to use safely.  The job of any callback is to create an IP and to call the FBP kernel.

Again, it makes total sense to build the app using call-returnless FBP, since the FBP paradigm fits perfectly into the asynchronous paradigm.

2.3 Multiple Processes / Threads / Cores / Distributed Processing

This will be discussed in a future article.  Note that Paul Morrison’s book http://www.jpaulmorrison.com/fbp/book.html is a good resource to read if you can’t wait for me to write about it.

I’m probably going to head in the direction of what does a small FBP-like kernel look like, without all of the bells and whistles of current hardware and OS’es, for the next while.

Roll Your Own

Rolling your own cpu faker.[1]

Let us imagine a 3-component FBP system.  Component A has one output pin and that pin is wired to the single input pin of Component B.  Both components are nested inside Component P, which has no pins.

P is the “top level” parent component of this simple system.

When the system is started, the “kernel” creates (“instantiates” in OO parlance) Component P.  P in turn creates (or asks the kernel to create) one A component and one B component and creates a wiring list (aka flow) that specifies the connection: “A’s output is connected to B’s input”.

Notice that, semantically, the wiring list belongs to the parent P.  A can’t “see” B and B cannot see A.

After initialization[2] the kernel calls the top level component and tells it to run.

Component P calls every one[3] of its components and tells them to run.

Let’s say, for argument, that Component B is called first.  It checks its input queue, finds nothing in it and simply returns (to the kernel).

Then Component A is called.  It doesn’t have an input queue, but it does have code that generates one output.  That output is bundled up into a simple data structure (IP, aka event) and enqueued on the appropriate output pin of A.  A then returns control flow to its parent P.

P looks around for more work.  It finds that there is an IP sitting on the output queue of A.  P pulls the IP off of the queue, checks its wiring lists, decides where the IP is destined and queues it up on B’s input queue.

P again looks around for more work.  It sees that B has something queued up on its input queue.  P calls B.  B pulls the IP off of its queue and processes it.  Then it returns to P.

P finds no more work pending on any of its children, so P returns to the kernel.

The End.

That was easy, and no processes were spawned in the process[sic].

Too easy?  No, the above “kernel” does the same things that a multi-processing kernel does – it treats apps as subroutines and calls them.

Finesse Points (asynch I/O, locking, prevention of recursion, etc.) will be discussed in subsequent articles.

[1] What I describe here is slightly different from FBP Classic, again for the sake of simplicity.  I hope to return to FBP Classic in a future article.

[2] Separating start-up from steady-state running is important in a system more complicated than the one described here.

[3] Clearly, this can be optimized.

Why is FBP Interesting?

So, we now know that processes / threads are a fiction.

Processes run on a single[1] CPU via timeslicing via the O/S – formerly known as a simple loader application.

Why is FBP interesting, since it runs on the same O/S as non-FBP software?

How does one implement FBP on a single CPU?  What if there are more cores, or distributed CPU’s?

FBP is meant to run on multiple CPUs.

Each FBP component gets its own CPU.  If I have an FBP program with 300 components, then – ideally – I should have 300 CPUs to run it on.

FBP is a paradigm shift in thinking about programming.

When we run FBP on a single-cpu paradigm O/S (formerly known as a simple loader application), we can maintain the FBP paradigm shift, but, we simply need to fake out the idea of multiple cpu’s.

By now, it should be “obvious” how this fake-out can be accomplished.

One way is to simply use the process model(s) provided by the hosting O/S (formerly known as a simple loader application), and put up with the incredible inefficiency piled upon this paradigm.

Another way is to roll-your-own FBP cpu-faker.

The roll-your-own method allows one to throw away all of the accumulated epicycles of the O/S model and to bring the O/S back into the realm of a simple loader application with a simple IP-transferring library (e.g. a queue).

I will describe the roll-your-own cpu-faker…

(If you run the roll-your-own cpu-faker within an O/S process, you get something very much like a Green Thread).

[1] Except when they run on multiple cores, given the preceding discussion using pet tricks that should be obvious.

Cornucopia of Epicycles

The way to combat slow external storage was to keep everything in memory.  Memory was about 1,000 times faster than various external storage schemes.

So, the epicycle of multi-tasking was invented.

If you had 10 users, each running their own app, you shoved all 10 apps into memory and let the CPU run the first program for a bit, then the second program for a bit and so on.

This idea created many new epicycles.

The program loader became a program scheduler, a distinguished application that determined which app was to be run for some amount of time – this became to be known as an Operating System (O/S), fundamentally, a fairly simple application.

Many programs were devoted to math loops and bit-spinning (e.g. waiting for the keyboard of one user).

People were already totally indoctrinated into the cult of single-cpu call-return programming.  They found it to difficult (unnecessary, unimaginable) to step back and think whether there was a different way to achieve the same goals, i.e. have many users running apps at the same time[1].

It became necessary – more epicycles – to invent relative addressing.  If HumanA’s program was loaded into slot 1 of the 10 app slots in memory on Monday, but on Wednesday it was loaded into slot 9, all of the addressing would be wrong.  All GOTO’s that worked on Monday would go to the wrong place on Wednesday.

So, the small, but distinguished application, now known as the O/S became more complicated.  As it loaded a program, it needed to fix-up every address in that program relative to its currently-loaded location in memory.

Then, of course, the software designers, the cult, leaned on hardware designers to take a load off of their hands.  Instead of doing the fix-ups in software, the CPU was tasked with this job.  The demands on the – single – CPU grew.  CPU’s needed to incorporate relative addressing (more registers, on-the-fly addition/subtraction of addresses relative to PC and SP, etc).

This, of course, made (single) CPU’s larger (2D area-wise) and more complicated.  Epicycle.

Oh yeah, and, programmers didn’t want to chop up their long-running loops.  So, the CPU / motherboard needed to incorporate a timer.

And the O/S – formerly known as a loader application – needed to add a new entry point – epicycle.  In addition to having an entry point for cold-boot and another for “yield” (formerly known as an O/S TRAP), it needed an entry point for time-slice.

When the time-slice interrupt fired, the O/S (formerly known as a simple loader application) would preserve the state of the currently-running app and load up the state of another app.

Oh, wait, and the CPU needed to be enhanced to support this kind of time-slicing activity.  It needed to automatically save some of the state of CPU on the current stack and hand off control to the time-slice entry point of the O/S (formerly known as a simple loader application) so that it could finish saving the complete state of the running process.

This, of course, made (single) CPU’s larger (2D area-wise) and more complicated.  Epicycle.

Then all hell broke loose.  The cult demanded hardware memory management – addresses faked via hardware intervention and traps when memory limits were not obeyed.  And, and, … caches, RISC, pipelines, priorities, etc, etc.

More epicycles.

All to support the cult/myth of the single CPU.

As the O/S – formerly known as a simple loader application – grew, software people started stumbling upon hidden interactions between all of the features of the O/S.

A new sacrament was born into the cult.

Programming with multiple processes was “hard”.  Race conditions, priority inversions.  Only gurus could handle this stuff correctly using very magical incantations[2].  Network protocols between CPU’s became even more magical and even more (apparently) difficult.

Sigh.

[1] Occam and Transputers were an early attempt to break this mold.  So was the Connection Machine.

[2] Well, not always.  Witness the Mars Rover fiasco, caused by a priority inversion.

The Black Monolith

… But, how could one timeslice a single CPU?

The software memory model was code at 0x0000, stack at 0xFFFF.  The answer was obvious.

While waiting for one human to enter a keystroke, switch programs and let another human enter a keystroke, and so on.

HumanA hits a key and the CPU needs to wait 20msec.  Slide HumanA’s program out to storage, then slide HumanB’s program into core and let it run for a bit.  Then, after 20msec, slide HumanB’s program out and slide back HumanA’s program in to run for a bit.

External storage was kind of slow in those days.  Needing msec’s of its own to operate.

What to do?

Invent epicycles.

Preserve the notion of a single CPU, being time-sliced across many users…