Hanois Tårne

Problemet

Som et eksempel på en mere avanceret anvendelse af procedurekald i den udvidede WinDavid-maskine vil vi se på Hanois Tårne. Vi skal her anvende maskinen med det udvidede instruktionssæt.

I dette problem har vi tre pinde (1, 2 og 3). På pind 1 er anbragt et antal (n) cirkulære skiver, alle med forskellig diameter, og således at enhver skive altid er mindre end skiven lige under den. Opgaven går nu ud på at flytte skiverne fra pind 1 til pind 3 under overholdelse af følgende regler:

En løsning

Man kan indse, at opgaven kan løses hvis vi kan Da underproblem 1 og 2 er af samme art som hovedproblemet men med én skive mindre kan de hver især løses på samme måde som hovedproblemet. I Pascal (Delphi) ser løsningen sådan ud:

program hanoi;
var
  n: integer;

procedure flyt(n, i, j: integer);
{Flytter n skiver fra pind nr. i til pind nr. j}
var
  via: integer;
begin
  if n=1 then
     flyts(i,j) {kan løses direkte}
  else begin
     via:= 6-i-j; {via-pindens nummer}
     flyt(n-1,i,via); {løsning af delproblem 1}
     flyts(i,j);      {flytning af nederste skive}
     flyt(n-1,via,j); {løsning af delproblem 2}
     end;
end; {flyt}

procedure flyts(i, j: integer);
{udskrive flytningen}

var
  x: integer;
begin
  writeln(i); {frapind}
  writeln(j); {tilpind}
  readln(x); {pause}
end;

begin
  readln(n); {antal skiver}
  flyt(n,1,3); {start løsningen}
end.
 

Activation record

Ved kald af en procedure vil vi opbygge en såkaldt Activation-record, der skal indeholde følgende oplysninger:
 
S: 

Q: 

 

lokale variable
...
Gammel Q
Returadresse
...
Parametre

Som det ses af ovenstående, vil vi bruge Q til at udpege vores activation-record med.

Før en procedure kaldes skal man altså anbringe parametrene på stakken med kommandoen TILS.
Dernæst kaldes proceduren med HSUB.

Proceduren skal indledes med instruktioner, der giver Q og S de rigtige værdier.
Selve procedurens instruktioner udføres.
Procedure afsluttes med instruktioner, der reetablerer Q og S.
Der vendes tilbage til kaldsstedet med HRET.

Efter procedurekaldet fjernes parametrene igen fra stakken.

Hovedprogrammet

Lad os først se på hovedprogrammet:

; start:
        n = 0
        IND n

        ; flyt(n,1,3)
        HENT n
        TILS        ; 1. par
        HENT #1
        TILS        ; 2. par
        HENT #3
        TILS        ; 3. par
        HSUB flyt
        STOP
 

Håndtering af stakken ved kald

Her ser vi, at der anbringes de tre parametre på stakken, der herefter ser sådan ud:
 
S:  3
1
n

Efter kaldet af flyt er stakken sådan ud:
 
S:  Returadresse
3
1
n

De to første linjer af flyt (se nedenfor) gemmer Q på stakken:
 
S: Gammel Q
Returadresse
3
1
n

De to næste linjer lader Q pege på vores activation-record (frame):
 
S: Q: Gammel Q
Returadresse
3
1
n

Endelig gør de to næste linjer plads til den lokale variabel:
 
S: 
Q:
Via (lokal var)
Gammel Q
Returadresse
3
1
n

Placeringen af de enkelte parametre og variable beskrives nu ud fra Q. F. eks. kan n hentes til A med instruktionen: HENT Q+4, og der gemmes i Via med instruktionen GEM Q+255.

Proceduren flyt

flyt:
        HENTQ
        TILS        ; q gemmes
        HENTS
        GEMQ        ; q peger på frame
        SUB #1
        GEMS        ; lokal var (via) på stak

        HENT Q+4    ; hent n
        SUB #1
        HNUL if1    ; if n=1 then
        HOP else1
if1:
        ; flyts(i,j)
        HENT Q+3    ; hent i
        TILS        ; 1. par
        HENT Q+2    ; hent j
        TILS        ; 2. par

        HSUB flyts
        FRAS        ; afstak parametre
        FRAS

        HOP end1
else1:
        ; flyt(n-1,i,6-i-j);
        HENT Q+4    ; n
        SUB #1      ; n-1
        TILS        ; 1. par
        HENT Q+3    ; i
        TILS        ; 2. par
        HENT #6
        SUB Q+3
        SUB Q+2
        GEM Q+255   ; via
        TILS        ; 3. par
        HSUB flyt
        FRAS        ; afstak parametre
        FRAS
        FRAS

        ; flyts(i,j)
        HENT Q+3    ; hent i
        TILS        ; 1. par
        HENT Q+2    ; hent j
        TILS        ; 2. par
        HSUB flyts
        FRAS        ; afstak parametre
        FRAS

        ; flyt(n-1,6-i-j,j);
        HENT Q+4    ; n
        SUB #1      ; n-1
        TILS        ; 1. par
        HENT Q+255  ; via
        TILS        ; 2. par
        HENT Q+2    ; j
        TILS        ; 3. par
        HSUB flyt
        FRAS        ; afstak parametre
        FRAS
        FRAS

end1:   HENTQ
        GEMS        ; genskab s
        FRAS
        GEMQ        ; genskab gl. q
        HRET

Håndtering af stakken ved returnering

Labelen end1 markerer slutningen af den egentlige programkode. Nu skal S og Q reetableres. Efter de to instruktioner HENTQ og GEMS ser stakken sådan ud:
 
S: Q: Gammel Q
Returadresse
3
1
n

Efter de to næste instruktioner har stakken følgende udseende:
 
S: Returadresse
3
1
n

Og efter HRET ser stakken sådan ud:
 
S:  3
1
n

Vi mangler blot at afstakke parametrene for at have fjernet alle spor af procedurekaldet.
 

Proceduren flyts

Procduren flyts ser sådan ud, og den bruger stakken på helt samme måde:

flyts:
        HENTQ
        TILS        ; q gemmes
        HENTS
        GEMQ        ; q peger på frame
        SUB #1
        GEMS        ; lokal var (x) på stak

        UD Q+3      ; udskriv i
        UD Q+2      ; udskriv j
        IND Q+255   ; pause

        HENTQ
        GEMS        ; genskab s
        FRAS
        GEMQ        ; genskab gl. q
        HRET