EXAMPLES OF ALGOL PROGRAMMING

THE FIRST TWO EXAMPLES ARE PROGRAMS WHICH PERFORM A TASK WHICH
IS MOST EASILY PROGRAMMED RECURSIVELY. THE FIRST ONE READS PAPER
TAPE AND PRODUCES AN OUTPUT TAPE ON WHICH THE PARITY BIT IS
SUCH THAT EACH FRAME HAS AN EVEN NUMBER OF HOLES. THE PRINCIPLE
IS THAT UNLESS THE CHARACTER IS ZERO, THE PARITY IS EVEN IF
THE LEAST SIGNIFICANT BIT HAS THE SAME PARITY AS THE REMAINING
BITS. THE PARITY OF THE LEAST SIGNIFICANT BIT IS FOUND IN THE
EXPRESSION (X-X%2*2) WHICH RETURNS EITHER 0 OR 1. THIS IS SUBTRACTED
FROM THE PARITY OF ALL THE MORE SIGNIFICANT BITS AND THE RESULT IS
ZERO IF THE PARITY IS EVEN, GIVING A ZERO NETT RESULT. THE PROCEDURE
PARITY WILL RECURSE THE SAME NUMBER OF TIMES AS THERE ARE ONES
IN THE CHARACTER.

'BEGIN''INTEGER' C;
'INTEGER''PROCEDURE' PARITY(X);
'VALUE' X; 'INTEGER' X;
'COMMENT' RESULT IS 1 IF ODD NUMBER OF BITS, ELSE 0;
PARITY:='IF' X=0 'THEN' 0
	'ELSE' ABS(PARITY(X%2)-(X-X%2*2));

LOOP:	C:=CHIN(2); C:=C-C%128*128;
	'COMMENT' THIS STRIPS OFF CHANNEL 8, IF PRESENT;
	CHOUT(2,C+128*PARITY(C));
'GOTO' LOOP;
'END'$$$

THE NEXT EXAMPLE IS A STATISTICAL TEST. OBSERVATIONS ARE MADE IN
PAIRS, THE FIRST OF EACH PAIR BELONGING TO ONE GROUP AND THE SECOND TO
ANOTHER. WE WISH TO FIND OUT IF THERE IS ANY DIFFERENCE BETWEEN THE
GROUPS. TO DO THIS WE FIRST FIND THE TOTAL DIFFERENCE BETWEEN THE
TWO GROUPS. WE THEN CALCULATE THE PROBABILITY OF GETTING THIS
DIFFERENCE BY CHANCE, IF THE PAIRS OF OBSERVATIONS HAD BEEN ASSIGNED
RANDOMLY TO EACH GROUP, RATHER THAN ALWAYS THE FIRST OF THE PAIR
TO THE FIRST GROUP. IF THERE ARE J PAIRS, THERE ARE 2^J WAYS OF
ASSIGNING THE PAIRS INTO THE GROUPS. EACH COMBINATIONS MUST BE TESTED
BY FINDING THE NETT DIFFERENCE BETWEEN THE GROUPS AND COUNTING THE
NUMBER OF OCCASIONS ON WHICH THIS DIFFERENCE IS GREATER OR EQUAL TO
THAT ACTUALLY OBSERVED. THIS COUNT DIVIDED BY 2^N IS
THE PROBABILITY OF OBSERVING THE DIFFERENCE BY CHANCE.  IN THE
PROGRAM, THE DIFFERENCES BETWEEN THE OBSERVATIONS IN EACH PAIR ARE
HELD IN THE ARRAY D. THE PROCEDURE BR ADDS TO THE SUM THE
DIFFERENCE INDICATED BY THE PARAMETER N WITH SIGN INDICATED BY S.
UNLESS N INDICATES THE LAST DIFFERENCE, IT GENERATES TWO MORE
SUMS, ONE WITH A POSITIVE DIFFERENCE AND ONE WITH A NEGATIVE
DIFFERENCE. EACH TIME N REACHES 1 THE TOTAL SUM IS CHECKED TO SEE
IF IT IS GREATER THAN OR EQUAL TO THE OBSERVED SUM OF DIFFERENCES.

TO SOLVE THIS PROBLEM WITHOUT RECURSION INVOLVES A NUMBER OF NESTED
'FOR' LOOPS EQUAL TO THE NUMBER OF DATA PAIRS. THUS, A SEPARATE
PROGRAM WOULD HAVE TO BE KEPT FOR EACH NUMBER OF DATA PAIRS. 

'BEGIN''INTEGER' I,J,COUNT;
'REAL' A,B,OBS;
'ARRAY' D[1:100];

'PROCEDURE' BR(N,S,SUM); 'VALUE' N,S,SUM;
'INTEGER' N,S; 'REAL' SUM;
'BEGIN' SUM:=SUM+D[N]*S;
'IF' N=1 'AND' ABS(SUM)>=ABS(OBS) 'THEN' COUNT:=COUNT+1
'ELSE''IF' N#1 'THEN''BEGIN' BR(N-1,+1,SUM); BR(N-1,-1,SUM)
	'END'
'END' BR;

SKIP(1); TEXT(1,"NUMBER OF PAIRS?"); J:=READ(1);
OBS:=0;
'FOR' I:=1 'STEP' 1 'UNTIL' J 'DO'
	'BEGIN' A:=READ(1); B:=READ(1);
	OBS:=OBS+A-B; D[I]:=ABS(A-B);
	'END';
SKIP(1); TEXT(1,"SUM OF DIFFERENCES"); RWRITE(1,OBS,10,2);
COUNT:=0; BR(J,-1,0); BR(J,+1,0);
SKIP(1);
TEXT(1,"PROBABILITY OF SAME OR GREATER WITH RANDOM SIGNS ");
RWRITE(1,COUNT/2^J,7,3);
'END'$$$

THE FINAL EXAMPLE IS A PROCEDURE FOR SOLVING SIMULTANEOUS EQUATIONS.
THE LEFT HAND SIDE MATRIX IS SET UP IN A TWO DIMENSIONAL
ARRAY A[ROW,COLUMN] AND THE RIGHT HAND SIDE IN A VECTOR B[ROW].
THESE NAMES OF THESE ARRAYS ARE PASSED TO THE PROCEDURE TO CORRESPOND
TO THE NAMES LHS AND RHS, TOGETHER WITH AN INTEGER GIVING THE NUMBER
OF EQUATIONS AND A LABEL TO EXIT TO IF THERE IS NO SOLUTION. THE
ANSWERS ARE LEFT IN THE RIGHT HAND SIDE VECTOR. THE METHOD USED IS
GAUSSIAN ELIMINATION WITH PARTIAL PIVOTING. UP TO ABOUT 30
EQUATIONS CAN BE SOLVED ON A PDP8 WITH 12K.


'PROCEDURE' SOLVE(ORDER,LHS,RHS,FAIL);
'VALUE' ORDER;
'INTEGER' ORDER; 'ARRAY' LHS,RHS;
'LABEL' FAIL;
'BEGIN'
'INTEGER' ROW,COL,ROW1,ORDER1,I,J;
'REAL' MAX;

'FOR' ORDER1:= ORDER 'STEP' -1 'UNTIL' 2 'DO'
'BEGIN'
MAX:=0.0;
'FOR' J:=1 'STEP' 1 'UNTIL' ORDER1 'DO'
'IF' ABS(LHS[J,ORDER1])>MAX 'THEN'
	'BEGIN' MAX:=ABS(LHS[J,ORDER1]); ROW:=J
	'END';
'IF' ROW#ORDER1 'THEN'
	'BEGIN' MAX:=RHS[ORDER1]; RHS[ORDER1]:=RHS[ROW];
	RHS[ROW]:=MAX;
	'FOR' COL:=1 'STEP' 1 'UNTIL' ORDER1 'DO'
	'BEGIN' MAX:=LHS[ORDER1,COL];
	LHS[ORDER1,COL]:=LHS[ROW,COL]; LHS[ROW,COL]:=MAX
	'END'
	'END' SWOP EQUATIONS;
'IF' LHS[ORDER1,ORDER1]=0 'THEN'
NOSOL:	'BEGIN' SKIP(1); TEXT(1,"NO SOLUTION"); 'GOTO' FAIL;
	'END';
'FOR' J:=1 'STEP' 1 'UNTIL' ORDER1-1 'DO'
'BEGIN'
MAX:=LHS[J,ORDER1]/LHS[ORDER1,ORDER1];
	RHS[J]:=RHS[J]-RHS[ORDER1]*MAX;
'FOR' COL:=1 'STEP' 1 'UNTIL' ORDER1 'DO'
	'BEGIN'
	LHS[J,COL]:=LHS[J,COL]-LHS[ORDER1,COL]*MAX;
	'END' ZERO ONE ELEMENT;
'END' ZERO ONE COLUMN
'END' TRIAGULARISE THE LEFT HAND SIDE;

'IF' LHS[1,1]=0 'THEN''GOTO' NOSOL;
'FOR' ROW:=1 'STEP' 1 'UNTIL' ORDER 'DO'
	'BEGIN'
	RHS[ROW]:=RHS[ROW]/LHS[ROW,ROW];
	'FOR' ROW1:=ROW+1 'STEP' 1 'UNTIL' ORDER 'DO'
	RHS[ROW1]:=RHS[ROW1]-LHS[ROW1,ROW]*RHS[ROW];
	'END';
'END' SOLVE SIMULTANEOUS EQUATIONS;