rcpt@eutrc4.urc.tue.nl (Piet Tutelaers) (08/04/89)
The Eight Queens Problem solved with COROUTINES crashes Logitech system!!!
The next program will run with the Logitech Modula-2 development system
version 3.0, BUT IF YOU REMOVE lines 3 and 69 of program Queens.mod the
program crashes and FUNNY things happen..... Can somebody explain why?
uucp: rcpt@eutrc3.UUCP | Piet Tutelaers Room RC 1.90
bitnet: rcpt@heithe5.BITNET | Eindhoven University of Technology
phone: +31 (0)40 474541 | P.O. Box 513, 5600 MB Eindhoven, NL
----------------------------Queens.mod-----------------------------------
MODULE Queens;
(* 3 *) FROM InOut IMPORT WriteString, WriteLn, WriteInt;
FROM Board IMPORT
Safe, (* tests if proposed placement is safe *)
Occupy, (* occupies a given place on the board *)
Vacate, (* vacates a given place on the board *)
Display; (* displays board *)
FROM SYSTEM IMPORT
PROCESS,
NEWPROCESS,
TRANSFER,
WORD,
ADR,
SIZE;
TYPE
Arow = [1..8];
Acol = [1..8];
CONST
wkspsize = 200; (* informed guess *)
VAR
colData:
ARRAY Acol OF
RECORD
cr: PROCESS;
wksp: ARRAY [1..wkspsize] OF WORD;
END;
initCol: Acol;
main: PROCESS;
done: BOOLEAN;
PROCEDURE Placer; (* coroutine code *)
VAR
myCol: Acol;
myRow: Arow;
BEGIN
myCol := initCol; TRANSFER(colData[myCol].cr, main);
LOOP
FOR myRow := 1 TO 8 DO
IF Safe(myCol, myRow) THEN
Occupy(myCol, myRow);
IF myCol < 8 THEN
TRANSFER(colData[myCol].cr, colData[myCol+1].cr);
ELSE
done:=TRUE;
TRANSFER(colData[myCol].cr, main)
END;
Vacate(myCol, myRow);
END
END;
(* none of the rows are safe in this column *)
IF myCol > 1 THEN
TRANSFER(colData[myCol].cr, colData[myCol-1].cr)
ELSE
done:=FALSE;
TRANSFER(colData[myCol].cr, main)
END
END
END Placer;
PROCEDURE Init;
BEGIN
FOR initCol := 1 TO 8 DO
(* 69*) WriteString('Initiating Placer '); WriteInt(initCol, 0); WriteLn;
WITH colData[initCol] DO
NEWPROCESS(Placer, ADR(wksp), SIZE(wksp), cr);
TRANSFER(main, cr)
END
END
END Init;
BEGIN
Init;
TRANSFER(main, colData[1].cr);
WHILE done DO
Display;
TRANSFER(main, colData[8].cr)
END
END Queens.
----------------------------Board.def-----------------------------------
DEFINITION MODULE Board;
EXPORT QUALIFIED Safe, Occupy, Vacate, Display;
PROCEDURE Safe(c, r: INTEGER): BOOLEAN;
(* Returns TRUE if the square on column c [1..8] and row r
[1..8] can be occupied by a queen.
*)
PROCEDURE Occupy(c, r: INTEGER);
(* Places a queen on the square [c,r] *)
PROCEDURE Vacate(c, r: INTEGER);
(* Removes queen from square [c,r] *)
PROCEDURE Display;
(* Displays a solution by printing the rows of queens on the succesive
columns
*)
END Board.
----------------------------Board.mod-----------------------------------
IMPLEMENTATION MODULE Board;
FROM InOut IMPORT WriteInt, WriteLn;
CONST
NROWS = 8;
VAR
k: INTEGER;
x: ARRAY [1..NROWS] OF INTEGER; (* x[i] row of queen in col i *)
row: ARRAY [1..NROWS] OF BOOLEAN; (* free row's *)
up: ARRAY [-(NROWS - 1)..(NROWS - 1)] OF BOOLEAN;
(* free upper diagonals *)
down: ARRAY [2..(2*NROWS)] OF BOOLEAN; (* free down diagonals *)
PROCEDURE Safe(c, r: INTEGER): BOOLEAN;
BEGIN
RETURN row[r] & up[c-r] & down[c+r]
END Safe;
PROCEDURE Occupy(c, r: INTEGER);
BEGIN
x[c]:=r; row[r]:=FALSE; up[c-r]:=FALSE; down[c+r]:=FALSE
END Occupy;
PROCEDURE Vacate(c, r: INTEGER);
BEGIN
down[c+r]:=TRUE; up[c-r]:=TRUE; row[r]:=TRUE
END Vacate;
PROCEDURE Display;
BEGIN
FOR k:=1 TO NROWS DO WriteInt(x[k], 3); END;
WriteLn
END Display;
BEGIN (* initiate empty board *)
FOR k:=1 TO NROWS DO row[k]:=TRUE END;
FOR k:=-(NROWS - 1) TO (NROWS - 1) DO up[k]:=TRUE END;
FOR k:=2 TO (2 * NROWS) DO down[k]:=TRUE END
END Board.ODX@PSUVM.BITNET (Tim Larson) (08/08/89)
In article <819@eutrc3.urc.tue.nl>, rcpt@eutrc4.urc.tue.nl (Piet Tutelaers) says: > >The Eight Queens Problem solved with COROUTINES crashes Logitech system!!! >The next program will run with the Logitech Modula-2 development system >version 3.0, BUT IF YOU REMOVE lines 3 and 69 of program Queens.mod the >program crashes and FUNNY things happen..... Can somebody explain why? > >uucp: rcpt@eutrc3.UUCP | Piet Tutelaers Room RC 1.90 >bitnet: rcpt@heithe5.BITNET | Eindhoven University of Technology >phone: +31 (0)40 474541 | P.O. Box 513, 5600 MB Eindhoven, NL >----------------------------Queens.mod----------------------------------- >MODULE Queens; > >(* 3 *) FROM InOut IMPORT WriteString, WriteLn, WriteInt; > . . . . > wkspsize = 200; (* informed guess *) > >VAR > colData: > ARRAY Acol OF > RECORD > cr: PROCESS; > wksp: ARRAY [1..wkspsize] OF WORD; > END; > initCol: Acol; . . . . > >PROCEDURE Init; >BEGIN > FOR initCol := 1 TO 8 DO >(* 69*) WriteString('Initiating Placer '); WriteInt(initCol, 0); WriteLn; > WITH colData[initCol] DO > NEWPROCESS(Placer, ADR(wksp), SIZE(wksp), cr); > TRANSFER(main, cr) > END > END >END Init; . . . . I compiled your code using JPI TopSpeed M2 and it worked identically (and correctly) with lines 3 and 69 and without them. I don't have the Logitech compiler anymore, but I used to work with it (I should say *argue* with it :-) and I still have the documentation. It seems to me that two possible things might be going on here, both of which should be easy to test (you may have tested them already, but just in case :-). One is that the compiler is trying to optimize the loop in Init, and is not updating the memory location of colData[initCol] soon enough (page 87 of User's Manual v3.0). You might try turning optimization off before the loop is entered. Otherwise, the work- space you are allocating may be too small (page 383 of User's Manual v3.0). You might try increasing wkspsize to 1024 or so, as it says near the middle of page 383. Sorry I couldn't be of more help, but maybe one of these ideas will work. Good luck, Tim Larson ODX@PSUVM.BITNET
randy@m2xenix.UUCP (Randy Bush) (08/15/89)
I played a bit with your Eight Queens program, and believe I can help explain the anomaly. First, I would warn that you had two FOR control variables that were not local to the immediate scope. Yes, loose compilers seem to allow this, but it is not legal. I also had to modernize the code a bit (SIZE is now a pervasive, and PROCESS has become ADDRESS). As to the problem, I believe it to be that the value of the global variable initCol, which is being used as a a FOR control variable, is being assigned to myCol in the coroutine procedure Placer. The compiler(s) having problems have probably stashed the FOR control value in a register and have not noticed the access within the coroutine as there was no blatant procedure call of Placer. Credit for detecting this problem should go to the OSI compiler for detecting a value strange error at the assignment to myCol. [Conflict of interest note: Although I no longer work at OSI, I did have just a bit to do with the implementation.] Hope this helps. randy -- uunet!tektronix ----\ sun!nosun --------- qiclab ---- m2xenix!randy or randy@m2xenix.uucp uunet!oresoft ------------------/
rcpt@eutrc4.urc.tue.nl (Piet Tutelaers) (08/15/89)
On my program Queens.mod (a solution of the 8 queens problem with coroutines), that crashes the Logitech 3.0 development system, I got the following suggestions: < I compiled your code using JPI TopSpeed M2 and it worked identically (and < correctly) with lines 3 and 69 and without them. I don't have the Logitech < compiler anymore, but I used to work with it (I should say *argue* with it :-) < and I still have the documentation. It seems to me that two possible things < might be going on here, both of which should be easy to test (you may have < tested them already, but just in case :-). One is that the compiler is trying < to optimize the loop in Init, and is not updating the memory location of < colData[initCol] soon enough (page 87 of User's Manual v3.0). You might try < turning optimization off before the loop is entered. I did, but this does not solve the problem. < .......... Otherwise, the work- < space you are allocating may be too small (page 383 of User's Manual v3.0). < You might try increasing wkspsize to 1024 or so, as it says near the middle < of page 383. I have played around with all kind of workspace sizes, but again without any success (the program with lines 3 and 69 added, runs within the given workspace 0f 200). < Sorry I couldn't be of more help, but maybe one of these ideas will work. < < Good luck, < Tim Larson < ODX@PSUVM.BITNET Thanks Tim for your suggestions Piet Tutelaers rcpt@eutrc3.UUCP