Graph Processor

Written by Amar Singh

This post is about choices presented to us when writing a program, how this affects the programmer’s ability to change the program.

Writing a program

Every programming language is a ‘tool’ for a particular task. - unknown

img

A programmer say, Bob writes a program say Chicken-counter to keep track of chickens on a farm. This program works well and Bob’s users are happy and submit regular feedback to Bob. Bob keeps improving features and fixing glitches.

After a few jolly months, Bob has spent some time with the problem domain, and is more suited to make better design choices of the program. Now, Bob can write a much better Chicken-counter program, based solely on the experience gathered from development and feedback from users, however is he able to do it?

Think for one second of the hundreds of choices that went into making the Chicken-counter program, that Bob and his colleagues made knowingly or unknowingly.

These choices appear in the following categories:

  1. Choice of datastructures
  2. Name of procedures aka. functions aka. instructions.
  3. The order of arguments
  4. Algorithms used

… and so on.

Consider the scheme procedure: chicken-count

(define (chicken-count x y)
"Count the number of chickens in hut X and hut Y."
  (if (hut-null? x)
    y
    (chicken-count (1- x)
      (1+ y))))

In defining a scheme procedure choices appear like so:

  1. Name of the procedure; ‘chicken-count’
  2. The order of arguments; ‘x’ then ‘y’. Thankfully, the names of the arguments are not important here. [Keyword arguments]
  3. Algorithm; f(x, y) {if x = 0; then y; f(x-1, y+1)}
  4. Datastructures; Integer x and y

An alternative,

(define (chicken-sum a)
  (lambda (b)
    (+ a b)))

Here we made slightly different choices,

  1. The name of the procedure is different.
  2. The order of arguments is different; ((chicken-sum a) b)
  3. Different choice of algorithm.

But we have kept the same datastructure of the hut, Integer.

Your mileage may vary according to the programming language you have in hand at the moment.

Programming model

Many programming languages have a concept of ‘data’ and ‘operations’ on data. Data may be called registers, variables, literals, objects. Operations may be called procedures, functions, methods. A programmer has to keep these models in his/her head when designing any program.

img

We can also take this model of programming in the mind of the programmer and write it down as a graph, where the Vertices or Nodes are ‘Data’ represented by objects, variables etc. and The edges or connections between these are ‘Operations’ represented by procedures, methods, functions etc.

;;; split the graph into
;;; 1. topology
(define g
  `((a b c e)
    (b a d)
    (c a f)
    (d b)
    (e a)
    (f)))

;;; 2. meaning of the symbols or types
(define t
  `((a . string)
    ...))

;;; 3. edges
(define e
  `(((a b) . ,string->symbol)
    ...))

When we are finished we have a description of ‘data’ of our program and the relations between these data.

  1. Named data-types.
  2. Relation between the data-types captured by procedures.

img

Then we can find a path from some data foo to bar by asking the program to traverse the graph g and build a procedure for transforming a string to keyword.

((graph-process g 'string 'keyword) "foo")

Flexibility

We have seperated the definitions of procedures from their application. One immediate concern is handling of procedures with different arities, this can be worked around by wrapping each procedure to accept a single stack as an argument and picking only those items from the stack that the procedure can accept and is allowed to take.

I intend to build a module in Guile scheme that allows one to program in this graph-processing-language. Currently it’s a part of another project, dubbed Resonance. My claim is that this approach will help write more flexible programs, and as a result more adaptable programs. Resonance, a version control system will be the testbed for it.

Inspirations

  • Revised Report on the Propagator Model
  • Lisp, the programming language.