Process

A process is the basic unit of computation in PARS; everything is about processes. A process is written by convention with a capital letter, e.g., P or Q, or as a word starting with a capital letter, e.g. MoveTo or Spin, or as all caps, e.g. AT. When you write 'a program' in PARS, what you do is to make a set of process definitions.

A process can execute for ever and never terminate. An example of such is the basic (which means predefined) process INF. The process INF will start and go on for ever, but not do any other computation or message passing. However, some processes do terminate. We distinguish two kinds of process termination: a successful termination or STOP and an unsuccessful termination or ABORT.

Consider an example where the process C evaluates some condition such as if two variables are equal, or if one is greater than the other, etc. This process C will always terminate, since for any two variables its always possible to determine the answer to a condition such as this. But if the condition evaluates to false, then the process will terminate in ABORT. If the condition evaluates to true, then it will terminate in STOP. This representation of termination status is the principal mechanism by which conditionality is represented in PARS (i.e., what would be a CASE or IF statement in a procedural language). But we'll see how that works later on.

Basic processes and Composite processes

Since everything you write in PARS is a process definition, you have to have some processes predefined a-priori, or else you can't ever write your first process definition in terms of anything else! The processes that are predefined are called basic processes. The set of basic processes usually depends on the domain of application: for example, a set of basic processes for a payroll program might be different than the set of basic processes for a web data mining application, or for a robot controller.

Since we are only interested in robot controllers, we only define a set of basic processes that are useful for building robot missions. The key thing about the set of basic processes when used to build a robot controller is that they must have been definied to the computer in some way other than PARS; for example, implemented in C or Python or Machine Code (or MissionLab/CNL).

In general we will use PARS to build two kinds of programs: The usual kind, where we are giving instructions to a computer to calculate something of interest (in the robot application domain, this will be a controller program for the robot), but also programs that are 'models' of physical phenomena. An example would be a PARS program for a robot: not the program that controls the robot! - we would call that one the controller - this one rather is the program that models how the robot would actually move! We will attack this in greater depth in a later section.

In building models of the physical world, predefinition of basic processes is not a restriction. For example, the location of the robot could be represented as a process called AT. There is no implementation of AT; instead we have decided that the process AT represents the location of the robot, in the same way that an engineer might decide that the value of the variable r represents the location of the robot. That is: it's a modelling decision.

All processes other than basic processes are referred to as composite processes and are defined in terms of either basic processes or other composite processes. So when you write a PARS 'program' the first thing you will write will be a composite process definition, and most likely using some basic processes.

Process Variables

All processes (basic and composite) can have state variables. Their number and type just depend on the basic process definition or, in the case of a composite process, whatever the programmer wants. We will typically write process variables using lowercase letters.

As an example, lets consider a process called P. Lets say that we would like P to have 2 variables, x and y. We write this in PARS as follows:

P<x,y>.

The angle brackets ('<' and '>') will be used to group state variables.

Exercise: Write down the definition of a process Q that has 3 variables called r, s and t.

Notice that we did not specify a type for these variables. PARS when written for papers etc is not typed. However, we do need to specify types for any real PARSfile that we write. There is a special compiler directive that is used to specify PARS variable types:

TYPE REAL x

specifies that the variable x is of type REAL.

TYPE VEC2F mu
TYPE VEC4F var
TYPE NORM d

specifies that mu is a 2D vector (over the reals), thar var is a 4D vector (over the reals) and that d is a random variable who value is represented as a Mixture of Gaussians distribution (MoG). The MoG is the only distribution that is currently implemented for random variables. Though clearly other distributions could be supported and would be useful: an exponential distribution for example.

Exercise: Write down the type definitions for the variables from the last exercise if r is a real, and s and t are random variables represented as MOGs.

Constant values can also be represented in PARS within PARSfiles as follows:

CONST VEC2F p0mean = (1,45.2)
CONST VEC4F p0var = (500,0,0,500)
CONST NORM p0 = (p0mean,p0var)

These three definitions define a 2D vector constant called p0mean with the value (1,45.2), a 4D vector p0var with the values indicated, and then define normal distribution constant p0 which is a single member MoG whose member has the mean p0mean and variance p0var.

Modification to the CONST syntax to allow multi-member MOG constants (9/18/14).

A MOG constant which has members that are the normal distributions S1, S2, S3 and S4 is specified as follows:

CONST MOG OBSTACLES=S1,S2,S3,S4

Each of the members ("peaks") needs to be defined as a normal constant as in the p0 example above. All the member are weighted equally. That is, for two members, each will have a weight of 0.5; for four members, each will have a weight of 0.25. Note: there is currently no syntax to describe a non-equally weighted MOG.

Note: 2D, 3D and 4D vectors can never be specified literally (ie you must always define a constant with that vector value, as above, and then give the name of the constant instead of the literal vector value, as e.g., in p0 above).

These are not serious implementation restrictions and just reflect the amount of time spent on the compiler so far. With enough need they can easily be addressed.

Process Expressions

A process expression is the key concept in defining a PARS process. A process expressions tells you how one process is defined in terms of other processes. In order to make a process expression you need two things:

1. A set of process composition operators
2. A syntax for defining process instances

Process Composition Operators

A process composition operator is a binary operator that takes two processes and returns a third, composite process. For example, ';' is the sequential composition operator. Let P and Q be two processes that have been defined. An example of a process expression is P ; Q. This is an expression that combines the process P and the process Q and makes a new process. In the case of ';' the new process behaves exactly the same as the first process, and when the first process STOPs (ends in a STOP), it then behaves like the second process until that terminates. However if the first process ABORTs (ends in ABORT) then the whole expression ABORTs.

Here are the key process composition operators:

1. Sequential composition ';' (defined above)
2. Parallel composition '|' - the expression behaves the same as both processes executing at the same time, taking the same time as the longer of the two processes, and ending in STOP if both do, otherwise ending in ABORT.
3. Disabling composition '#' - the expression behaves the same as both processes executing at the same time, but if any process terminates it causes the other to ABORT.

Process Instance

A process instance is a process whose variables have been given values. Consider the example of the process P which has two REAL variables x and y. We can write an instance of P as P<10,11>, this instance has been initialized with x=10 and y=11. As P executes, these values might change of course. But the process instance contains enough information for the process to start executing.

Exercise: Write an instance of the process P that has values x=5.4 and y=6.5.

Answer

Exercise: Make up a process name for a process that has 3 REAL variables and specify two instances of that process.

Answer

Process Definitions

We now have sufficient background to be able to specify some composite processes! Lets say we have the following basic processes:

P<x,y>.

Q<r,s,t>.

W< q >.

Notice the syntax for defining a basic process. The process name is given, followed by the list of process variables, followed by a period ('.'). All PARS definitions end with a period.

We can now define a new, composite process T< a > as follows:

T< a >=P< a, 2*a > ; W< 10+a >.

First of all, notice the syntax: The new process name is given (T) followed by its list of variables (a). The equal sign ('=') indicates the definition is starting, and the period ('.') marks the end of the definition. Between the '=' and the period '.' there can be any process expression.

In this case, the process expression consists of a sequential composition (';') of two processes instances. The instance of P is specified to have initial values x=a and y=2*a, that is x has the same value as the parameter a was given, and y has the same value as 2*a. The process instance of W is given an initial value for its variable of q=10+a.

Exercise: Write a process definition for a process Z with four arguments, which consists of a sequential composition of an instance of P given the first two arguments as initial values, and a second instance of P given the second two values as initial parameters.

Answer

Of course, process definitions can be complicated. Consider the folllowing definition

T< a > = P<1,0> ; ( W< a > # ( Q<a,0,0> | Q<a,1,1> | Q<,2,2> ) ).

Here, parenthesis are used to group subparts of the process expression. Three instances of the process Q are executed in parallel. An instance of the process W is executed in a disabling composition with these three: that means, if W terminates, it forces the others to terminate as well. The first process to be executed is P. If P terminates in STOP, then the remainder is executed. Otherwise T ends when P aborts.

Examples of Common Expressions

Let us consider a class of basic processes called condition processes. A condition process evaluates a condition on its arguments and terminates with STOP if it's true and ABORT otherwise. For example:

1. GTR<a,b> evaluates a>b
2. GTE<a,b>, a > = b
3. LTR<a,b>, a < b
4. LTE<a,b>, a < = b
5. EQ<a,b>, a = b
6. NEQ<a,b>, a ! = b

The following process expression is the equivalent of the IF statement: IF (a=b) THEN P ELSE Q;

( EQ<a,b> ; P | NEQ<a,b> ; Q )

Since EQ only terminates in STOP if a=b, then P is only carried out if a=b. Similarly, Q is only reached if NEQ terminates in STOP, i.e., if a!=b.

NOTE: There is no need for the branches of the statement to be disjoint as in an IF statement. For example,

( LTR<a,b> ; P | LTE<a,b> ; Q )

is the same as Q if a=b, but is P|Q if a<b.

The following is the equivalent of SWITCH(a) { CASE 1: P1; CASE 2: P2 ... }

( EQ<a,1> ; P1 | EQ<a,2> ; P2 | ... )

Once again, the cases don't have to be disjoint.

However, it is difficult to specify an OTHERWISE:Q or DEFAULT: Q case, without having to list all the conditions

(NEQ<a,1>|NEQ<a,2>|.....) ; Q

Exercise: Write a PARS process that has two process variables, and will do P if the first variable is the larger and Q if the second is the larger, but nothing if they are equal.

Answer

Looping

There is only one way to have things repeat in PARS and that is to specify a recursive process. A recusive process is one that 'calls itself.' Consider the following example:

T< a > = P< a > ; T< a+1 >.

The process T is defined as a sequential composition of the process instance P with its variable initialized to a, and if that STOPs, then an instance of T (that's the recursive call right there) with its variable initialized to the value of a plus 1. The process P (in this case) is called the body if the recursive process - it is what will be repeated each time.

Consider the case where we have

P< a > = NEQ<a,10>

and we have an instance of T<0> executed. In that case, we have

T< 0 > = P< 0 > ; T <0+1>.

= NEQ<0,10> ; T< 1 >.

= NEQ<0,10> ; NEQ<1,10> ; T< 2 >.

= NEQ<0,10> ; NEQ<1,10> ;......................................; NEQ<10,10>.

(where ..................... stands for the remaining expansions of NEQ from 2 through 9.) Since NEQ<10,10> will fail, ie will terminate in ABORT, we know the process composition will stop at that point.

This process is called unwinding the recursion (it can be done with loops too). We only do it here to show the meaning of the recursion, and how it implements a 'loop.'

In fact, this is an example of Tail Recursion, that is, recursion where the recursive call is the last step in the definition. PARS supports recursion anywhere in the definition of course, but Tail Recursion is particularly useful.

The following expression is the equivalent of a WHILE loop with a condition C and a body B:

T<a,b> = C<a,b> ; B<a,b> ; T< ... >.

where '...' in this case stands for some modification to a and b for the next iteration.

The following is the equivalent of a DO WHILE loop with condition C and body B

T<a,b> = B<a,b> ; C<a,b> ; T< ... > .

The only difference is that B is done once before the condition is tested, just as in a DO WHILE loop.

Exercise: Write a recursive process that (a) never terminates and (b) terminates after 1 iteration of its body.

Answer

Result Variables

So far, processes can take initial values, and can end in STOP or ABORT. But that termination condition is the only 'effect' of a process. We now introduce a way for a process to return a value or tuple of values.

The process ADD has two variables, x and y, and returns a third variable z. We write this as:

ADD< x,y >< z >.

The result variables are just specified as a list after the variable list. We introduce a useful basic process PASS with one input and one result variable as follows

PASS< x >< y >.

PASS just passes on to y whatever it got in x. That may not seem too useful, but in fact it helps us a lot. We can now define ADD in the following way:

ADD<x,y>< z > = PASS<x+y>< z >.

Exercise: Use tail recursion and PASS to build a process that raises its first argument to the power of the second, assuming that the first is a real number and the second is a positive integer.

Answer

Communication

The functional style of programming that we have defined so far is indeed very useful on its own. But it is a simplified view of concurrent programming because two concurrent process P and Q can never communicate with each other.

We now introduce the idea of communication ports. These are zero-buffered communication end-points (like sockets). To be used for message passing, ports have to be connected to other ports, making a communication channel.

The process P which has variables x and y and result z, and which has one input port called a, and one output port called b, is written as follows:

P<x,y>(a)(b).

Regular parenthesis are used to group the lists of input port names (i.e., a), which come first in the definition, and output port names (i.e. b), which come second. The two lists come between the list of variables and the list of results. This ordering reinforces the fact that communications on a and b occur while P is executing, whereas the initial values are given to x and y before P starts executing, and the result value z is given when P terminates.

There are two syntax issues that need to be covered with respect to port communications:

1. How does a process read and write values from/to ports?
2. How can a programmer specify what ports are connected to what other ports?

Reading and Writing from/to Ports

We introduce two basic processes for reading and writing from/to ports. The process

IN< a >< v >

reads a value from the port a and passes that on in its result variable v. The process

OUT<b,v>

writes the value v to the port b. Both processes only terminate if and when the communication finishes. So when IN terminates in STOP, the communication has ocurred. When OUT terminates in STOP, the communication has occurred. Otherwise the processes just wait. Possibly forever.

Example

The following process repeatedly writes a value to its port (forever).

W< a >()(p) = OUT<p,a> ; W< a > .

Note that we have to specify the empty list '()' for input ports of T, since otherwise we can't specify an output port list. Note also that we don't specify the list of results if there aren't any.

The following is a process that repeatedly reads on its port (forever).

R< x >(b) = IN< b >< v > ; R< v > .

Note there are no output ports, so we only specified an input port list. The value that is read from the port is passed on as the initial value of the variable x. Its not used for anything here, but it illustrates how to pass on the value read.

Exercise: Write a process WR that reads a value on its input port and that writes that same value to its output port - forever.

Answer

Connecting Ports Together

Processes behave very differently depending on what their ports are connected to! Consider the processes R and W defined in the previous example. Lets write a process expression where we make an instance of each of these and connect the ports together so that what is written by R will be read by W:

T = R< 0 >(c1) | W()(c1) .

The instances now have their port lists, in the same order as for a definition, as well as their initial variable values. However, what appears in a port list for a process instance is called a connection label. The label c1 appears in the first input port location for R and in the first output port location for W. This indicates that the first input port of R is connected with the first output port of W (and furthermore that the connection channel is to called c1, but we won't use that information).

Environment Models:

An environment model is a PARS program that models an environment phenomenon. It is a causal model for example in the same sense that a spring is modelled by the algebraic expression

f = k x

that is, given an input length x and knowledge of the spring constant k, the force exerted by the spring f is calculated. The PARS model is very similar

Spring(x)(f) = IN< x >< v > ; OUT<f,k*x> ; Spring .

A simple model for a robot would take a velocity command and then determine where the robot should be once a discrete time step has elapsed. (A model without a discrete time step is possible but more difficult to write.)

The robot will be modelled as a single point that can move in any direction at any speed. The only state will be the position of the robot p and the new position will be specified by the difference equation:

p(t+tc) = p(t) + u(t)*tc

where tc is a time constant, the smallest interval between motions, p(t) is the value of the position at time t, and u(t) is the vallue of the velocity at time t. Our PARS model is therefore:

Robot< p,u >(vel)(pos) = (AT< p > # OUT< pos,r > # IN< vel >< u > ); DELAY< tc > ; Robot< p+u*tc > .

The disabling composition ('#') is identical to parallel, except that the first process to terminate, terminates the rest. So the subexpression of Robot between parens "(" and ")" consists of AT< p > representing the state of the robot being at the position p, and a transmission of the position on port pos if any processes wants to read it, and an input of a new velocity on port vel, if any process wants to send it. Since AT will never terminate, this subexpression only terminates if an OUT sends the position out, or if an IN gets a new position. In either case, the DELAY process then represents the passing of a time tc, which here is assumed to be a constant (defined previously with CONST REAL tc= some value). The recursion then 'calculates' the new position of the robot as its current position plus the velocity times the time constant.

If no other process reads or writes to this process, then nothing happens! If a process just reads the input port then we get some motion. So a system consisting of

SYS = R<0>(c1) | Robot<p0,0>()(c1)

consists of an instance of R process defined in the previous two subsections with an instance of Robot, and with the output of Robot connected to the input of R. The initial position is p=p0 and initial velocity is 0.

Robot would recurse once for each read of its output port in the following sequence of recursive calls:

Robot<p0,0>, Robot<p0+0*tc>, Robot <p0+0*tc+0*tc>,......

If we just look look at the AT and DELAY processes, then we would get the following sequence

AT ; DELAY ; AT<p0+0*tc> ; DELAY ; AT<p0+0*tc+0*tc> ....

Not so interesting since it only represents the non-motion of the robot!

However, consider the following SYS

START< v >()(op) = OUT<op,v> .

SYS = (START<5>()(c2) ; R<0>(c1)) | Robot<p0,0>(c2)(c1) .

Now we have built a little robot controller. It starts by issuing a velocity command of value 5 and then just reads the robot position.

If we consider how robot now recurses we would have

Robot<p0,0>, Robot<p0,5>, Robot<p0+5*tc>, Robot <p0+5*tc+5*tc>,......

If we just look look at the AT and DELAY processes, then we would get the following sequence

AT ; DELAY ; AT<p0+5*tc> ; DELAY ; AT<p0+5*tc+5*tc> ....

This sequence represents the motion of the robot from p0 with velocity 5.

NOTE: It is possible to use PARS as if it were a discrete simulation language. That is not the objective. The objective is to extract the 'generator' of the above sequence of AT and DELAY so that its possible analyze properties of that sequence without ever executing it. These generators are called 'flow functions.' They can be extracted with some ease from a set of tail-recursive processes (now you know why all the recursive definitions are tail -recursive!)

So from the perspective of VIPARS: We NEVER want to execute any PARS program - only to use it as a stepping stone for verification.

Other Topics

Other topics to be added to the tutorial include

Flow Functions

Flow functions can be extracted from a set of tail recursive definitions. The programmer doesn't need to do anything to specify a flow function or to guarantee that flow functions can be obtained other than to write a tail recursive process definition.

VIPARS:

this tool accepts a subset of PARS programs written with certain conventions and does formal verification on the programs.

Sysgen This is a VIPARS algorithm that takes a set of concurrent, communicating tail recursive process definitions and reassembles them as a single composite tail recursive process. This can only be done if the message passing between component processes can be lined up into a single large 'body.' So if there are some unconnected ports that engage in IN or OUT operations, the algorithm will report back a failure since the unconnected ports will result in a deadlock.

In fact this could be generalized to extract the largest set of processes which could be synchronized into a single composite 'body' - but some work would need to be done for that.

Flogen

This is a VIPARS algorithm that looks at how variables are modified in the set of concurent, communicating processes that is the 'body' generated by Sysgen. Flogen can generate the set of flow functions for the composite body, where the flow functions include variable calculations within processes and by message passing between processes.

-- (c) Fordham University Robotics and Computer Vision