{ L.A. Dept Computer Science, Monash University 17/9/87
   generators by coroutines, uncurried for Pascal
   n queens problem

see L.Allison. Continuations implement generators and streams.
    Computer Journal 33(5) 460-465 1990

Cont = State -> Answer      where State=List,  Answer=Std_output
Generator = Cont -> State -> Answer = Cont -> Cont

------------------------------------------------------------------------------}

program generate(input,output);

type list = ^ node;
     node = record hd:integer; tl:list end;

var n :integer;

function cons(i:integer; L:list):list;
  var p:list;
begin new(p); p^.hd:=i; p^.tl:=L; cons:=p
end;

{-----------------------------------------------------------------------------}
                                                          {generator "library"}
{ success :Cont }
procedure success(L:list);

  procedure print(L:list);
  begin if L<>nil then begin write(L^.hd:3); print(L^.tl)
  end                  end;

begin if L<>nil then
      begin writeln; write(' :'); print(L)
end   end {success};

{ choose :Int -> Cont -> Cont = Int -> Generator }
procedure choose(n:integer; procedure cont(L:list); L:list);
  var i:integer;
begin for i:=1 to n do cont(    cons(i, L) )
    { for each i       continue with i++L }
end {choose};

{ filter :(State->boolean) -> Generator }
procedure filter(function p(L:list):boolean;
                 procedure cont(L:list);
                 L:list);
begin if p(L) then cont(L)       { else fail }
    { if L ok then continue with L else do nothing }
end;

{ doo = gen**n :Int -> Generator -> Generator }
procedure doo(n:integer;
              procedure gen(procedure cont(L:list); L:list);
              procedure cont(L:list);
              L:list);

  procedure gencont(L:list);
  begin gen(         cont,    L)
      { gen and then cont, to L }
  end;

begin if n=0 then cont(L)
      else doo(n-1, gen,          gencont,               L)
         { do (n-1) gen and then [gen and then cont], to L }
end {doo};

{-----------------------------------------------------------------------------}
                                                              {n queens proper}
procedure queen(n:integer);

   function valid(L:list):boolean;

     function v(col:integer; L2:list):boolean;
       begin if L2=nil
             then    v:=true                    { safe }
             else if (L^.hd=L2^.hd) or          { check rows  }
                     (L2^.hd+col=L^.hd) or      { & diagonals }
                     (L2^.hd-col=L^.hd)         { other diags }
             then    v:=false                   { threat }
             else    v:=v(col+1, L2^.tl)
       end {v};

   begin if L=nil then valid:=true
          else valid:=v(1, L^.tl)
   end {valid};

  { choosevalid :Generator }
  procedure choosevalid(procedure cont(L:list); L:list);

    procedure validcont(L:list);
    begin filter(valid,          cont,          L)
         { check valid and if so continue, with L }
    end;

  begin choose(n,                 validcont,                       L)
      { choose row and then [check valid and if so continue], with L }
  end {choosevalid};

begin doo(n,       choosevalid,                  success, nil)
   { [do  n times: choose a valid row] and if so succeed }
end { queen };

begin
  writeln(' type n<eoln>');
  while not eof do
  begin readln(n); queen(n); writeln
  end
end.

{\fB Generators by Continuations in Pascal. \fP}
{ Released under GNU General Public Licence (GPL). }
{ NB. Requires a full ISO standard Pascal Implementation. }