Understanding ASTRA Execution

Now that we have some basic understanding of ASTRA programs, it is a good idea to reflect on what it all means in terms of control flow and how that control flow relates to other programming paradigm.

At its heart, ASTRA, and all AgentSpeak(L) implementations, are event-based concurrent programming languages where global state is modeled using predicate logic and behaviour is encapsulates within a set of contextual event rules.  But what does this mean practically?

One commonly presented view of Agent-Oriented Programming (AOP) is as a specialisation of Object-Oriented Programming (OOP) where the state is more constrained, and message types are restricted to performatives. However, this tells only part of the story as agents are also a concurrent programming paradigm.  In the case of ASTRA, individual agents can be viewed as being equivalent to processes and the intentions of the agent are threads.

To understand this, we need to reflect on how ASTRA programs work. ASTRA agents basically react to events. Events arise from changes in the environment, receipt of messages, or as a result of the invocation of a sub goal.  Events trigger behaviours that define how the agent should respond to the event. Events can be overloaded  – more than one behaviours  can be linked to an event.  The selection of a specific behaviour is based on rule-order and an associated context that defines when the behaviour should be considered.  Behaviours are synonymous with methods / procedures and are encoded in plan rules that combine a triggering event, a context, and the implementation of the behaviour. When an agent selects a behaviour to handle an event, an intention is created.  With the exception of sub goal events, all events generate a new intention. Sub goal events are similar to method calls, and affect the intention that they were invoked from.

Intentions are the concept in ASTRA that correlates with method/procedure execution. An intention is basically a stack that is similar in structure and purpose to a call stack. It is used to maintain the current state of the intention.  Each iteration of the ASTRA interpreter, one intention is selected and the next statement in the behaviour is executed. When there is only a single intention, this means that the behaviour is executed in isolation. However, when there are multiple intentions, the execution is interleaved. ASTRA adopts a round-robin policy, ensuring that all intentions receive an equal opportunity for execution. It is this interleaving of intentions that motivates the mapping of intentions to threads.

Race Conditions and ASTRA

If intentions are equivalent to threads then it is normal to expect that race conditions could arise.  In mainstream programming languages race conditions often take the form:

fetches ct = 0 
B fetches ct = 0 
A computes the value ct++ = 1 
A stores the value 1 in ct 
B computes new value ct++ = 1 
B stores the value 1 in ct

In ASTRA, such a program would look something like this:

agent Racy {
    module Console C;
    module System S;

    initial ct(0);
    initial !init(), !init();

    rule +!init() {
        query(ct(int X));
        +ct(X+1);
        -ct(X);
    }

    rule +ct(int X) {
        C.println(S.name() + ": X = " + X);
    }
}

This program invokes the !init() goal twice creating 2 intentions and generates the following output:

CHANGING LOGGING LEVEL
Event: +!main([]) was not handled
main: X = 0
main: X = 1

Notice that  the value of X is updated only once – this is because both intentions update ct(X) to be the same, so the second update is ignored (the agent already believes it so it does not result in a new belief added event).

Synchronized Blocks

To facilitate removal of race conditions, ASTRA includes support for synchronized blocks. A synchronized block is a section of the behaviour code that is labelled as a critical zone. This code can only be executed by a single intention at a time. Synchronized blocks are declared using the synchronized keyword but also require an identifier to act as a token for the block.  This allows multiple synchronized blocks to be declared representing a common critical zone.  Once an intention enters a synchronized block, all synchronized blocks with the same identifier are locked and cannot be entered until the current intention is completed.  Synchronized blocks are local to a single agent, they do not work across agents (i.e. two agents that are running  the same agent program can be in the same critical region at the same time).  To provide inter-agent mutual exclusion, a distributed mutual exclusion algorithm must be used.

The code below removes the race condition from the example program above:

agent Racy {
    module Console C;
    module System S;

    initial ct(0);
    initial !init(), !init();

    rule +!init() {
        synchronized (ct_tok) {
            query(ct(int X));
            +ct(X+1);
            -ct(X);
        }
    }

    rule +ct(int X) {
        C.println(S.name() + ": X = " + X);
    }
}

This program invokes the !init() goal twice creating 2 intentions and generates the following output:

CHANGING LOGGING LEVEL
Event: +!main([]) was not handled
main: X = 0
main: X = 1
main: X = 2

This is the expected output.