Richard Harter’s World
Site map
Comp. Sci.
Ocotober 2010
Email

Flow based naive recursive fibonacci function

Below is some code in a non existent language that resembles the proposed San language. It implements a flow based version of the naive recursive fibonacci function, e.g.,

    fibonacci (n) 
        if (n <2) return n
        else return fibonacci(n-1)+fibonacci(n-2)
In essence the code replaces function calls by spawning sub processes, passing data to them, having the sub processes pass results back and then commit suicide. This is not a good thing to do, but then neither is the naive recursion. The point is to illustrate an appoach. The code is followed by notes.
01    Define_auton fibonacci
02        Initialization
03            in0       = Define_inport (Data,Mtype.integer)
04            in1       = Define_inport (Data,Mtype.integer)
05            out0      = Define_outport(Data,Mtype.integer)
06            out1      = Define_outport(Data,Mtype.integer)
07            out2      = Define_outport(Data,Mtype.integer)
08            sum,count = 0
09        From in0 -> n
10            If (n <= 2) done(n)
11            Send n-1 -> make_child(out1,in1).in0
12            Send n-2 -> make_child(out2,in1).in0
13        From in1 -> n
14            sum += n
15            if (count == 1) done(sum)
16            count = 1
17            End
18        Procedure make_child(from_parent,to_parent)
19            child = Spawn(fibonacci)
20            Connect from_parent -> child.in0
21            Connect child.out0  -> to_parent
22            Return child
23            End
24        Procedure done n
25            Send n -> out1
26            Die
27        End fibonacci
Line 01: Auton = FBP components. There is a code convention that user variables and names are in lower case. System commands and variables have an initial capital letter. End of line terminates statements.

Line 02: The statements in the initialization block are executed when the auton is spawned.

Line 03: Inport is an abbreviation for input port. Similarly outport is an abbreviation for output port. Define_inport returns a handle to an inport. The arguments are as follows:

Argument one specifies whether the information being delivered as data or as a document. Documents are Morrison’s information packets. Only one physical copy exists at a time; documents are passed by shallow copy. Multiple copies of data can exist; data is passed by deep copy. There are various obvious implications.

Argument two specifies the message type (message = information packet). My view is that messages should be strongly typed and that emissions to outports must have the same type as the receiving inports. The system variable, Mtype, holds labels for the established types.

Line 09: The “From” segments are event handlers where events are inputs coming into a port. This is a fairly natural interpretation. I’m using arrows where there is flow into and out of the auton.

The code uses “no loop” input response functions, i.e., a “From” block only processes one packet when activated. Suppose we want “loop” response functions that process packet after packet until there is no more input. A good way to do this is to use data streams, i.e., the message type has the stream attribute. Code might look this:

    From port -> x
        While (x)
            # process x (the current instance)
            Next x # Get next instance, if any
            End while
        End from
An alternative is to feed all inputs into a single stream and have a single master loop. The loop body selects the appropriate response code. This style is used in functional language implementations, e.g. Erlang.

Line 10: I am assuming that compilation/interpretation is multi-pass; procedure done does not have to be defined before it is used.

Line 17: The code uses the “unnecessary end statements can be omitted” convention. From blocks cannot be nested; ergo no end statement is needed. On the other hand procedures can be nested so preceding end statements are needed.

Line 19: Unlike FBP with a static flow graph the assumption here is that the flow graph is dynamic, i.e., new nodes in the graph can be created, old ones deleted, and conncections can change over time.

I assume a hierarchical (mini) process model similar to unix and friends, with the following modifications: A parent process can create connections to and from itself and spawned children. Furthermore processes (except root processes) can spawn siblings as well as children. This is a complication but I feel it is an important requirement; consider the issues in modelling bacterial colonies evolving over time.

As with unix processes, killing a process recursively kills all of its child processes. In addition a process can commit suicide.

One nice thing about this approach is that it provides natural hierarchy even if the flow graph is static.


This page was last updated October, 2010.

Richard Harter’s World
Site map
Comp. Sci.
Ocotober 2010
Email