PGA Toolset - User Manual

1. Introduction
2. Tools
2.1. Generic Parser
2.2. Projections
2.3. Generic Simulator
2.4. Bisimulation Tester
2.5. Parallel Simulator
2.6. Unit Operator
2.7. PGLA Jump Optimizer
2.8. Combining Programs and State Machines
2.8.1. Adding State Machines
2.9. Thread Simulator
3. Program Notations
3.1. PGLA
3.2. PGLB
3.3. PGLC
3.4. PGLD
3.5. PGLDg
3.6. PGLE
3.7. PGLEc
3.8. PGLEcw
3.9. PGLEcr
3.10. PGLEcm
4. Basic Instruction Sets
4.1. Generic
4.2. Molecular Programming Primitives
4.3. MPP with Values
4.4. Highlevel MPPV
4.5. Garbage collection
4.6. Molecular Scripting Primitives
4.7. MSPea
4.8. MSPio
4.9. HMPPV with inverse selection
4.10. MSPfunc
References

B. Diertens
University of Amsterdam
Faculty of Science

1. Introduction

Program Algebra (PGA) is an algebraic framework for sequential programming. It is intended to contribute to a better understanding of sequential programming. A very simple program notation is used as basis for development of other program notations.

The syntax of program expressions in PGA is generated from a set of constants, the primitive instructions, and two composition mechanisms. The primitive instructions have as parameter a set of basic instructions. These basic instructions can be viewed as requests to an environment to provide some service. Upon execution, a basic instructions returns a boolean value.

Primitive instructions:

a basic instruction: a

After performing the basic instruction a execution continues with the next instruction.

termination: !

Execution stops.

positive test: +a

If the basic instruction a returns true, execution is continued with the next instruction. If it returns false, the next instruction is skipped.

negative test: -a

If the basic instruction a returns false, execution is continued with the next instruction. If it returns true, the next instruction is skipped.

forward jump: #k

The instruction itself and the following k - 1 instructions are skipped. If k is 0, a jump to the instruction itself is made.

Compositions:

concatenation of X and Y: X;Y

repetition of X: X ω

On top of PGA, other program notation are designed, which can be mapped on PGA. Such a mapping is called a projection. Several projections to intermediate languages may be used to get the result that is needed.

2. Tools

2.1. Generic Parser

The generic parser is meant to be an easy checker for a program in any program notation. By providing modules for the programming language and basic instructions set one can add its own program notation. Currently the following programming languages are supported:

PGLA, PGLB, PGLC, PGLD, PGLDg, PGLE, PGLEc, PGLEcw, PGLEcr, PGLEcm

And the following basic instruction sets are supported:

Generic, MPP, MPPV, HMPPV, FMN, MSP, MSPea, MSPio, HMPPVis, MSPfunc

The generic parse can be invoked with the command

genparser program

As default it uses PGLA as programming language and Generic as basic instruction set. This basic instruction set accepts any string of characters.

The generic parser has the following options:

-v

verbose; show what is going on.

-p

print the program as parsed with line numbers and label information.

-P

programming-language

Specifies the programming language.

-B

basic-instructions

Specifies the basic instructions.

-L

library-path

library-path is added to the search-path for the Perl modules for the programming language and basic instructions.

2.2. Projections

A projection is a translation from one program notation to another that is lower in the hierarchy of program notations.

The following projections are available:

pglb2pgla, pglc2pglb, pgld2pglc, pgldg2pgld, pgle2pgldg, pglec2pgle, pglecw2pglec, pglecr2pglec, pglecm2pglecr

They all read from standard input and write to standard output, for example

pglb2pgla < input > output

translates input in PGLB to output in PGLA.

Since they read from standard input and write to standard output, they can be used as filters in composite commands like:

pgld2pglc < input | pglc2pglb | pglb2pgla > output

Note that pglecm2pglecr must always be used in combination with pglecr2pglec because the first one makes use of a stack that is introduced with the latter.

There is a program available called project that sorts out which projections must be used. It may be used as follows

project from to < input > output

For example,

project pglecm pgla < input > output

translates input in PGLEcm to output in PGLA. When given the option -p, project outputs only the command it uses for the translation. So,

project -p pglec pgla

outputs

cat | pglec2pgle | pgle2pgldg | pgldg2pgld | pgld2pglc | pglc2pglb | pglb2pgla

When given the option -l it outputs the hierarchy of program notations it knows about.

pglecm -> pglecr -> pglec -> pgle -> pgldg -> pgld -> pglc -> pglb -> pgla
pglecw -> pglec -> pgle -> pgldg -> pgld -> pglc -> pglb -> pgla

2.3. Generic Simulator

A typical invocating of the generic simulator is

gensim -v -l program

As default it uses PGLA as programming language and MPP as basic instruction set.

The generic simulator has a textual user interface with the following commands:

l file

load program from file and make it the current one.

l

list loaded programs.

lc

name

make program name the current if previously loaded.

list

list current program.

r

run current program. Running can be stopped by Ctrl-C, and continued by another r.

r

name

make program name the current if previously loaded, and run it.

rr

rerun: reset and run

s

step: execute a single instruction.

e

action

execute action.

reset

reset program counter.

t + /

-

set tracing on/off.

b + /

- n

set/unset breakpoint on line n.

b

list breakpoints.

b c

clear all breakpoints.

i

initialize core.

d

dump core

u + /

-

enables/disables updates of fluid during a command (speeds up execution considerably).

q

quit.

The generic simulator can be started with a graphical instead of a textual user interface with the use of the option -g. The graphical user interface consist of a Command, Console, and a Program window.

A listing of the current program is always provided in the Program window. The selection of the current program that is already been loaded can be done in this window too. Breakpoints can be set and unset by clicking on a line in the listing of the program.

The generic simulator can be invoked with the following options:

-f

a graphical view of the fluid is given. (deprecated, use -v)

-fs

size

the fontsize in the graphical fluid is set to size.

-g

a graphical user interface is started.

-l

file

loads file (may be given more than once).

-n

no display of foci that are null in the graphical fluid.

-v

a graphical view of the core of the basic instruction is given (if available).

-P

programming-language

Specifies the programming language.

-B

basic-instructions

Specifies the basic instructions.

-L

library-path

library-path is added to the search-path for the Perl modules for the programming language and basic instructions.

Further arguments are treated as files containing simulator commands which are executed in order.

The graphical fluid can be resized and scrolled by the scrollbars or with the use of mouse-button 2 (click and drag). A print can be made with mouse-button 3 or with Ctrl-P.

2.4. Bisimulation Tester

In order to test for bisimulation of two programs, the programs have to be converted to a labelled transition system (LTS) with the program prog2lts It can be invoked as

prog2lts program > lts-file

As default it uses PGLA as programming language. The program to LTS converter has the following options:

-P programming-language

Specifies the programming language. Currently only support for PGLA, and PGLEc is available.

-L library-path

library-path is added to the search-path for the Perl modules language.pm and languageTransSystem.pm. This option can be given more than once.

The bisimulator tester can be invoked as follows.

bisim lts-file1 lts-file2

2.5. Parallel Simulator

The parallel simulator is a controller that can start several simulators that work on one core of the basic instruction set. For instance,

parsim -l a -l b

will start a simulator with program a and a simulator with program b. It also starts an interface from which new simulators can be started with a particular programming language and program (not necessary).

The parallel simulator can be invoked with the following options:

-P programming-language

Specifies the programming language.

-B basic-instructions:

Specifies the basic instructions.

-l file

starts a simulator which loads file (may be given more than once).

2.6. Unit Operator

In [1] PGLA is extended with the unit operator and are several embeddings and projections given in order to translate this into PGLA.

For this purpose, the following programming languages are added:

PGLAu - PGLA with unit operator,
PGLBu
- PGLB with unit operator
PGLBg
- PGLB with goto’s and labels instead of forward and backward jumps.

And the following projections/embeddings:

pglau2pglbu, pglbu2pglbg, pglbg2pglb.

So elemination of the unit operator can be done with the command:

pglau2pglbu < input | pglbu2pglbg | pglbg2pglb | pglb2pgla > output

For convenience the tool pglau2pgla is provided which invokes the above command.

There is also a tool pglau2pglb provided that does the job of three in one go. And in combination with pglb2pgla does the whole job.

2.7. PGLA Jump Optimizer

Programs translated to PGLA probably contain a lot of unnecessary jumps. Consecutive jumps that can be done with one jump, jumps to the following instruction, and jumps that are not used at all. pgla-jumpopt optimizes and eliminates these. It can be invoked as:

pgla-jumpopt < input > output

2.8. Combining Programs and State Machines

In [2] the interaction of programs and state machines is introduced. To interact with state machines (or co-programs), the basic instruction set FMN (Focus Method Notation) is added. It contains the following instructions:

method call: f.a(x)
Where f is the focus of the instruction, and a(x) its co-instruction part (or co-action). The bracket pair can be empty. A focus is loaded the first time it is used.
It returns the value replied by the co-instruction.

prefixed method call: f.p:a(x)
Here, p is the prefix of the action that will be performed, indicating a particular copy of the state machine. A copy of the state machines is created the first time the prefix is used.
It returns the value replied by the co-instruction.

Alternative versions, which resembles the Focus Method Notation described in [3] :

method call: f.a:x

instance method call: f:i.a:x

In the following a description of the state machines provided with the toolset are given. Where not mentioned, the co-actions return the value true.

Console
Co-actions: println(s) in which s is a string of characters
The action println prints its argument.

smbr − boolean register
Co-actions: set(true), set(false), eq(true), eq(false)
The co-actions set(true) and set(false) reply true. The co-actions eq(true) and eq(false) reply false until the register is set, after which eq(b) replies true whenever b is the current value of the register, and false otherwise.

smnnr − natural number register
Co-actions: set(i), eq(i) in which i is a natural number
The replies of the co-actions are simular to that of smbr.

smnnc − natural number counter
Co-actions: succ(), pred(), isZero()
The counter always starts with value zero, and the action pred() leaves the counter at zero if it is zero.

smnns − natural number stack
Co-action: push(i), pop(), topEq(i) in which i is a natural number
The stack always starts empty, and the action pop() leaves the empty stack empty.

For example, consider the following PGLEc program.

smbr.x:set(true);
smbr.y:set(false);
+ smbr.x:eq(true) {;
    Console.println(x is true);
}{;
    Console.println(x is false);
};
+ smbr.y:eq(true) {;
    Console.println(y is true);
}{;
    Console.println(y is false);
}

Upon execution the result will be:

x is true
y is false

2.8.1. Adding State Machines

For using other state machines than the default, the generic simulator has been provided with the option:

-CL colibrary-path

colibrary-path is added to the search-path for the Perl modules that implement a state machine. This option can be given more than once.

A state machine must have at least the method new, since this method will be used by the simulator for initializing the state machine. Furthermore, it is convenient to provide a method dump, which prints the state on standard error, to make testing easier.

2.9. Thread Simulator

The thread simulator can run several thread, each in their own simulato, and control them by using a certain strategy. This strategy can be chosen by the user.

The thread simulator can be invoked with the following options:

-P programming-language

Specifies the programming language.

-B basic-instructions:

Specifies the basic instructions.

-l file

starts a thread simulator which loads file (may be given more than once).

-b -i

Steps with a strategy can either be instructions (-i) or behavior or basic instructions (-b, the default).

New threads can be started with the instruction fork #k but then the programming language has to be extended with thread instructions in the following way

-P programming-language:Thr

3. Program Notations

3.1. PGLA

PGLA consist of the following instructions:

void basic instruction: any element from the parameter set of basic instructions.
When executed these instructions may modify a state, a boolean value being generated in addition. The attribute void expresses that these instruction do not make use of the returned boolean value.

termination instruction: !
Indicates termination of the program.

positive test instruction: +a
When the basic instruction a returns true, execution continues with the next instruction. When false is returned the next instruction is skipped.

negative test instruction: -a
When the basic instruction a returns false, execution continues with the next instruction. When true is returned the next instruction is skipped.

forward jump instruction: #k
Denotes a jump of length k. It skips itself and the next k - 1 instructions.

repeat instruction: \\#k
A program ending with \\#k will repeat its last k instructions, meaning an endless repetition of the last k instructions.

3.2. PGLB

In addition to the instructions of PGLA, PGLB has the instruction:

backward jump: \#k
Jumps back k instructions.

With this instruction the repeat instruction of PGLA is redundant and is not included in PGLB.

3.3. PGLC

PGLC is a minor variation on PGLB. It has no explecit termination instruction. Termination takes place when the last action in the list has been executed (and was no backward jump) or when a forward or backward jump is made to an instruction outside the list.

3.4. PGLD

PGLD is PGLC without the forward and backward jumps, but with:

absolute jump: ##k
It jumps to (the beginning of) the k-th instruction of the program.

3.5. PGLDg

PGLDg is PGLD with the following instructions:

termination instruction: !
Reintroduced.

label catch instruction: Lk
Here is k a natural number. As an action it is a skip.

absolute goto instruction: ##Lk
Jumps to the first (i.e. the left-most) label catch instruction with the label k.

3.6. PGLE

PGLE is a sublanguage of PGLDg. The only restriction is that each test instruction (positive or negative) must always be immediately followed by a goto instruction, or a termination instruction.

3.7. PGLEc

PGLEc is PGLE extended with the following constructions:

conditional instruction: +a{ or -a{
Both forms initiate the text of a conditional construct.

then/else separator: }{

end brace: }
Closes the conditional construct.

3.8. PGLEcw

PGLEcw extends PGLEc with while loops.

conditional while start: +a{* or -a{*

unconditional while start: {*

while end: *}

3.9. PGLEcr

PGLEcr extends PGLEc with recursion. For a projection to PGLEc a stack is needed, so it must be used in combination with a basic instruction set with which that can be build.

returning goto: R##Lk
Perform a jump to the label catch instruction with the label k.

return: R
Jump to the instruction just after the last returning goto instruction to which a return has not yet taken place.

3.10. PGLEcm

PGLEcm extends PGLEc with method calls. For a projection to PGLEc, the projection to PGLEcr can be used.

method definition: m(arg1,...,argn){;...;}

method call: m(v1,...vn)

assign method call: y=m(v1,...,vn)

object method call: obj.m(v1,...,vn)

assign object method call: y=obj.m(v1,...vn)

4. Basic Instruction Sets

4.1. Generic

Although this is not a basic instruction set meant to be executed, the user can do so anyway for testing purposes.

Actions are not really executed, but only a boolean reply is given. In the case of the textual user interface the reply is always true. When the graphical user interface is used action are displayed and the reply value can be set.

4.2. Molecular Programming Primitives

Molecular Programming Primitives (MPP) is a basic instruction based on the modelling of the memory state of a system as a fluid as described in [4].

Mutations

atom creation: x = new
Create a new atom and bring it into focus x.
Always returns true.

field introduction: x.+f
Introduce a reflexive field f for the atom in focus x.
Returns true if the atom focussed by x does not yet own a field named f, otherwise returns false.

field withdrawal: x.-f
Remove the field f from the atom in focus x.
Returns true if the atom focussed by x owns a field f, otherwise returns false.

field mutation: x.f = y
Place the atom focussed by y in the field f of the atom in focus x. Returns true if the atom focussed by x owns a field named f, otherwise returns false.

Assignments

field selection: x = y.f
Bring the atom in field f of the atom in focus y into focus x.
Returns true if the atom focussed by y owns a field named f, otherwise returns false.

assignment: x = y
Place the atom in focus y also in focus x.
Always returns true.

Tests

atom identity test: x == y
Returns true if the foci x and y share an atom, otherwise returns false.

field membership test: x/f
Returns true if f is a field of the atom in focus x, otherwise returns false.

MPP is extended with garbage collection
instructions.

4.3. MPP with Values

MPPV extends MPP with instructions for dealing with values. Currently the types int (non-negative integer) and bool (boolean) are supported.

Mutations

value field introduction: x.+f:t
Introduce a new value field f of type t (int or bool) for the atom in focus x. The value will be initialized by a type dependent label (0 for int, false for bool).
Returns true if the atom focussed by x does not yet own a field f, otherwise returns false.

value field mutation: x.f = y
Replace the label of the value contained in field f by the label of the value in focus t. Replace means copy and not share the label.
Returns true if the atom focussed by x owns a field f of the appropriate type, otherwise returns false.

Assignments

value field selection: x = y.f
Bring a copy of the value in field f of the atom inf focus y into focus x.
Returns true if the atom focussed by y owns a field f, otherwise returns false.

value assignment: x = y
Put a copy of the value in focus y in focus x.
Always returns true.

constant value assignment: x = u
Place a value with label u in focus x.
Always returns true.

Tests

value identity test: x == y
Returns true if the values in the foci x and y carry the same labels, otherwise returns false.

constant value identity test: x == u
Returns true if the value in focus x carries the label u, otherwise returns false.

MPPV is extended with garbage collection
instructions.

4.4. Highlevel MPPV

HMPPV is an extension of MPPV (see [5]). It provides all kinds of instructions that are combinations of instructions from MPPV. Also a type str (string) for values is added. A string must be surrounded by double quotes ("). These are not part of the string. New value fields of type string are initialized with the empty string (""). A double quote and a backslash (\) inside a string must be escaped with an additional backslash in front of them.
In the following list of possible instructions, object is used to denote either a focus or a field selection. A field selection may be compound (e.g. x.f.g).

object = new
object
= object
object
.+f
object
.+f = new
object
.+f = object
object
.+f:t
object
.+f:t = u
object
.+f:t = object
object
.-f
object
/f
object
== object

object?
Returns true when the value selected by object is an atom, and false otherwise.

object?t
Returns true when the value selected by object is of the type t, and false otherwise.

HMPPV is extended with garbage collection
instructions.

4.5. Garbage collection

remove focus: rma x
If the atom in focus x has no other references to it, it is removed and focus x is set to null.
Returns true when the atom in focus x is removed, otherwise returns false.

restricted garbage collection: rgc
Removes all atoms that have no references to it. This is done repeatedly until no more atoms can be removed. This process will not remove all garbage: cycles in the reference structure will be left intact.
Always returns true.

full garbage collection: fgc
Removes all garbage including reference structures with cycles.
Always returns true.

4.6. Molecular Scripting Primitives

Molecular Scripting Primitives (MSP) is an extension of HMPPV with instructions that operate on values (see [5]).

Operations on numbers:

incr object
Increments the integer value selected by object with 1.

incr object n
Increments the integer value selected by object with n.

incr object1 object2
Increments the integer value selected by object1 with the integer value selected by object2.

decr object
Decrements the integer value selected by object with 1. Return false if the value was already 0.

decr object n
Decrements the integer value selected by object with n if the value is larger than or equal to n. Returns false otherwise.

decr object1 object2
Decrements the integer value selected by object1 with the integer value selected by object2 if it is larger than or equal to the value it must be decremented with. Returns false otherwise.

Operations on strings:

first object1 object2
Takes the first character of the string selected by object1 and assign it as a string of length 1 to object2. If the selected string is the empty string, false is returned.

delfirst object
Removes the first character from the string selected by object. If the string is the empty, false is returned.

append object1 object2
Appends the string selected by object2 to the end of the string selected by object1.

Type conversions:

int object1 object2
Converts the string selected by object1 to an integer value and assigns it to object2. If no integer value can be obtained from the string, false is returned.

str object1 object2
Converts the integer value selected by object1 to a string and assigns it to object2.

4.7. MSPea

MSPea (MSP with evaluation/apply) is an extension of MSP, which gives the possiblity to execute arbitrary code.

compile object
Compiles the string selected by object into a molecule and assigns it to object. It is capable of compiling strings representing programs in the programming language PGLA with MSP as basic instruction set. Returns false when there are errors detected.

apply object
If object is a string, it is executed as a basic instruction and returns the value returned by the basic instruction. And otherwise it fails.

eval object
If object is a string, it compiles the string into a molecule, after which the molecule is evaluated. If object is an atom, it is evaluated. And otherwise evaluation fails. It does no assignment of the molecule to object like compile does. The returned value of eval is the returned value of the last evaluated basic instruction.

4.8. MSPio

MSPio is an extension of MSP with instructions for input and output (see [6]).

read object
Deletes the first character (actually a string with length 1) from the string in focus INPUT and puts it in object.

write object
Appends the string denoted by object to the string in focus OUTPUT.

4.9. HMPPV with inverse selection

HMPPVis is an extension of HMPPV with inverse selection. Inverse selection is a mechanism for selecting a certain field between two objects. The construction

object1 - object2

selects the field that selects object1 from object2 . Inverse selection can be used everywhere were a field selection can be used. For example:

x.(y.f-z) = k.f.(z.f-l.g).(m.g-n.f)

4.10. MSPfunc

MSPfunc (MSP with functions) is an extension of MSPea, which gives the possiblity to define and execute functions (see [7]).

function fname(parameters):type string
Defines the function fname with optional parameters and optional return type. The string denotes the body of the function in one of the programming language PGLA or PGLEc with MSPfunc as basic instruction set. PGLEc can only be used as programming language when this language is used as programming language for the whole program. PGLA is used in all other cases. The string is compiled into a molecule and assigned to the focus fname. The parameters are added to this molecule.
The parameters must be a comma separated list in which each parameter is denoted as identifier:type. A parameter can be referenced by <>.identifier. Local variables can be added with <>.+identifier and <>.identifier:type, and referenced in the same way as the parameters.
In the case that the function is given a return-type, the statement return object/value can be used. The return ends the execution of the function only in PGLEc, it does not end the exececution of the function in PGLA.
In the case of PGLEc, the labels used are only local.

fname(arguments)
Executes the function fname by binding the arguments to the parameters and evaluating the molecule in the focus fname.

object = fname(arguments)
Executes the function fname by binding the arguments to the parameters and evaluating the molecule in the focus fname. After execution the value in the return statement is assigned to object.

References

1.

A. Ponse, “Program algebra with unit instruction operators,” Journal of Logic and Algebraic Programming 51(2), pp. 157-174 (2002).

2.

J.A. Bergstra and A. Ponse, “Combining programs and state machines,” Journal of Logic and Algebraic Programming 51(2), pp. 175-192 (2002).

3.

J.A. Bergstra and M.E. Loots, “Program algebra for sequential code,” Journal of Logic and Algebraic Programming 51(2), pp. 125-156 (2002).

4.

J.A. Bergstra and I. Bethke, “Molecular dynamics,” Journal of Logic and Algebraic Programming 51(2), pp. 193-214 (2002).

5.

B. Diertens, “Molecular Scripting Primitives,” electronic report PRG0401, Programming Research Group - University of Amsterdam (June 2004).

6.

B. Diertens, “A Compiler-projection from PGLEc.MSPio to Parrot,” electronic report PRG0403, Programming Research Group - University of Amsterdam (October 2004).

7.

B. Diertens, “Molecular Scripting Primitives with Functions,” electronic report TCS1504, section Theory of Computer Science - University of Amsterdam (June 2015).