Programming Gannet

The key to understanding how Gannet programs are executed is this: a Gannet program is a tree of function calls and when executing a program, the Gannet machine evaluates all branches of the tree concurrently. As a result there is not particular evaluation order, i.e. you cannot assume that one argument of a function is evaluated before another.

Deferred Evaluating: Quoting

This behaviour can be changed by quoting the arguments. However, all quoting does is defer the evaluation of the expression to the function body. It is then up to the service implementing the function body to evaluate the quoted expression. This is very similar to Scheme's delay/force mechanism, or to Perl's eval.

; Scheme
(define a 10) 
(define eval-aplus2 (delay (+ a 2)))
(define a 20) (force eval-aplus2) => 22

# Perl
my $a=10;
my $aplus2 = '$a+2';
$a=20;
eval($aplus2); => 22

A consequence of Gannet's eager evaluation mechanism is that any symbol that cannot be evaluated must be quoted. This includes numbers: from Gannet's perspective, unquoted numbers are symbols and it will try to evaluate them -- and fail. Hence, numbers should be quoted:

(* '6 '7)

Another key difference between Gannet and other languages is that the Gannet services that provide the functionality are not themselves written in Gannet, as in general they will be hardware or software cores obtained from third parties. For details about creating your own services see Creating Services.

Gannet Labels

Every expression in a Gannet program can be labelled. A label is simply a named reference to an expression. Labels are a compile-time feature, they are completely static and immutable. The syntax for labels is very simple:

(label l42 (* '6 '7))

Note that the labeling does not stop the expression from being evaluated. To defer evaluation, quote the expresssion:

'(label l42 (* '6 '7))

This results in the label l42 refering to the unquoted expression but the original expression will not be evaluated.
Note that currently, only unquoted expressions can be labelled, i,e. the following do not work:

(label l42 '(* '6 '7)) ; => compiler error
(label l42 '42)        ; => compiler error

It is valid to use labels recursively, i.e.

(label infinity (+ '1 infinity))

is valid and will recurse forever -- or at least until the stack overflows. We will see further on how to construct infinite loops that do not result in stack overflow.

Control Services

As most developers will want to concentrate on creating the computational services for their particular system, the Gannet distribution provides a number of control services which provide the familiar flow control constructs. The core set of control constructs is:

The if and return constructs

Gannet's if returns the value of its second or third argument predicated on the value of the first argument:

(if (S_cond ... ) (S_t ...) (S_f ...))

If none of arguments is quoted, both branches will be evaluated in parallel with the predicate expression. Although this is the fastest approach, it is generally not what you want (or at least what other languages do). To evalute the selected branch based on the value of the predicate, the branches must be quoted:

(if (S_cond ... ) '(S_t ...) '(S_f ...))    

A special construct often used in conjunction with if is return. This construct simply returns the value of its first argument. If the argument is quoted, the return body will take care of the evaluation. The reason for using return is that it can be used to quote a branch without quoting the actual expression in the branch:

(if (S_cond)
    '(return (S_t ...))
    '(return (S_f ...))
)

This is particularly useful if for some reason the argument of return is itself quoted, as there is no other way in Gannet to "stack" quotes. Reasons for quoting the argument of return will be covered in Advanced Topics.

Grouping and lexically scoped variables: begin, let, assign, read

Gannet has two different grouping constructs, begin and let. The begin construct takes an arbitrary number of arguments and returns the value of the last argument. Quoting arguments of begin means that the expressions will simply not be evaluated. As a result, if the last argument is quoted, begin will return a reference to the quoted expression. (As the Gannet machines stores all references as 32-bit unsigned integers, the return value will be a large positive integer.) The begin construct does not give scope, nor does it bind variable. However, a common use is for grouping labelled expressions:

(begin
    '(label e1 (* '5 '7))
    '(label e2 (+ '3 '4))
    (+ e1 e2)
)   

The other grouping construct is let, which is similar to Scheme's let in that is provides the scope for binding lexical variables, but is unlike Scheme's let in that it is not syntactic sugar for lambda. The let construct has another main use: it can be used to sequence operations. Quoted expression inside a let will be evaluated in lexical order but after the unquoted ones (which are evaluated without order. Variables are assigned using assign and accessed using read or simply by evaluation:

(let
    (assign 'x '6)
    (assign 'y '7)
    (* x y)
)

The difference between using (read 'x) and x is that the read call will simply fail if the variable had not been assigned while the evaluation will block until the variable has been assigned. In other words, read only works if we can sequence the assignments first:

(let
    (assign 'x '6)
    '(assign 'y (+ (read 'x) '1)
    '(* (read 'x) (read 'y))
)

Although the use of mutable variables is generally not a good idea in a functional language, especially with concurrent evaluation, variables can be reassigned using update.

(let
    '(assign 'a '1)
    '(update 'a (+ (read 'a) '1)
    '(* (read 'a) '2)
)

Functions: lambda and apply

Functions in Gannet are defined using lambda and applied using apply. The lambda construct returns an unnamed function which can be bound to a label or variable:

(let
    '(label mult (lambda 'x 'y '(* x y)))
    '(apply mult '6 '7) ; => 42
)

(let
    '(assign 'mult (lambda 'x 'y '(* x y)))
    '(apply (read 'mult) '6 '7) ; => 42
)

A very important limitation of the apply construct is that it only accepts quoted expressions as arguments. The reason for this is that apply constructs the actual expression by substituting the lambda-variables by the argument symbols which represent the quoted expressions (rather than by binding the lambda variables to the evaluated expressions).

Lists operations

[To be added]

Advanced Topics

Result redirection

Gannet is designed for programming the data flow between IP cores in SoCs. The control services add flow control to the system, resulting in a highly flexible reconfigurable system. However, the actual control services could become performance bottlenecks if the data would flow throught them as well. To avoid this, Gannet has a mechanism for result redirection. The mechanism only works for quoted arguments, hence its name 'deferred evalation and result redirection'.

For example, in

(S1 (if (S_cond ...) '(S_t ...) '(S_f ...)))

the result of the call to S_t or S_f will be sent directly to S1, bypassing if. Similarly, in

(S1
    (let
        '(assign 'x '6)
        '(S2 x)
    )
)

the result of the call to S2 will go straight to S1. However, this implies that the let subtask should not exit before S2 has exited. For that reason, S2 will send an 'ack' packet to let when it has finished, indicating to let that it's OK to exit (and free the variables).

Loops and Tail recursion

The main reason for allowing variable updates is to construct finite loops using label. For example, a factorial can be implemented as:

(let
    '(assign 'n '10)
    '(assign 'acc '1)
    '(label loop (if (< n '1)
                '(return acc)
                '(let  
                    '(update 'n (- (read 'n) '1)) 
                    '(update 'acc (* (read 'acc) (read 'n)))
                    '(return 'loop)
                )
            ))
 )

However, the issues with this loop is that the inner let call will fill up the equivalent of the 'stack' in the Gannet machine. This is because the result redirection mechanism will prevent let from exiting until it receives an 'ack'. However, if the recursion uses proper tail calls, there is no need for the intermediate 'ack' as every iteration will reuse the same subtask. For that reason, for proper tail calls the 'ack' mechanism can be disabled. The result is that the let will exit without waiting for the 'ack', and so the stack will not fill up.

To indicate that a recursion has proper tail-call behaviour, the tail call is suffixed with tc:

(label 'loop (if (cond)
            '(return ...)
            '(returntc 'loop ...)
         )
)

Tailcall-versions exists for if, return, let and apply.

Buffers and Pipelining

Many Systems-on-Chip perform streaming data processing, e.g. audio or video processing. Efficient streaming data processing requires pipelining, i.e. buffers are inserted between the operations so that every operation can be performed on the processed result of the previous operation (similar to an assembly line). This design pattern is virtually unknown in most programming languages intended for von Neumann-style microprocessors, as it is only of use in systems with multiple independent processing units (e.g. multicore systems).

Gannet supports pipelining through a single-element buffer. The following example is a simple example of pipelining of matrix operations. The service (a) returns a stream of 8x8 matrices as used e.g. in MPEG encoding.

(let
    '(buf 'b1 (a))
    '(buf 'b2 (tran (stream 'b1)))
    '(label L 
        (returntc 'L (scale '2 (stream 'b2)))
    )
)    

Buffers are implemented in the Service Manager, consequently the buf and stream calls are not service calls but rather modifiers of service calls. In the example, the matrix generated by (a) is stored in the buffer b1; the stream command retrieves the value from the buffer and at the same time restarts the task, i.e. (a) is called again. The labeled returntc call is a simple infinite loop.