4 november 1963

Over stapeladministratie

1. Binnenblokken, procedureblokken en blokhoogte.

	Het begrip blok is louter lexicographisch. Het hele programma is per definitie een blok,
binnen in een blok kunnen een of meer andere blokken gedefinieerd worden.
Behalve de ALGOL-blokken voeren wij nog in :
a) een procedure-declaratie is per definitie een blok
b) een for-statement is per definitie een blok.

	Wij onderscheiden nu twee soorten blokken :
a) procedureblokken
b) alle overige blokken ; deze noemen wij "binnenblokken".

Opm. Wij laten voorlopig even buiten beschouwing of we de procedure body als binnenblok van het
procedureblok beschouwen.

	De aldus ingevoerde blokken hebben de eigenschap, dat elk blok met uitzondering van het
programma-blok in een ander blok gedefinieerd is. We voeren nu in het begrip "blokhoogte", dwz.
het programma-blok krijgt blokhoogte 0. Elk ander blok krijgt een blokhoogte 1 hoger dan die van
het lexicographisch onmiddellijk omvattende blok.

2. Binnentophoogte en display.

	Aan elk procedureblok kennen we toe een zg. "binnentophoogte". Ook de binnentophoogte
is een zuiver lexicographisch begrip : de binnentophoogte is 1 meer dan de maximum blokhoogte
in het inwendige van het procedureblok zonder dat het in een daarin inwendig procedureblok zit.
(Andere definitie : het is 1 meer dan de maximum inwendig voorkomende blokhoogte na verwijdering
van alle erin voorkomende proceduredeclaraties.)

	Binnenblokken hebben de eigenschap, dat men ze slechts vanuit het onmiddellijk omvattende
blok kan binnengaan, dit in tegenstelling tot procedureblokken.

	Bij binnenkomst van een procedureblok, en alleen dan, zullen we een nieuwe display invoeren.
De lengte van deze display kiezen we gelijk aan de binnentophoogte, dwz. groot genoeg om te
garanderen, dat we erin de ruimte hebben om (zie onder) de binnenblokken van deze procedure
te kunnen behandelen.

	De opmerking is nl. dat de techniek van de MC1-vertaler voor ingaan en uitgaan van een
binnenblok echt wel efficient is. De MC1-vertaler werkt met een vaste display. Bij binnenkomst
hoef je alleen een nieuw element in de display in te vullen en de stapelwijzer op te hogen, bij
verlating hoef je alleen de stapelwijzer af te lagen (en displayelement te negeren, maar dat
kost niet zo'n moeite.)

	Hebben we echter, als in de MC1-vertaler een enkele display, dan hebben we om de
haverklap de plicht tot de operatie UDD (Up Date Display). De bewering is, dat slechts een
nieuwe display invoeren bij binnenkomst van het procedureblok voldoende is om alle
UDD-operaties kwijt te zijn - dwz. te kunnen condenseren tot wisseling van L.

3. De werkruimtewijzer WW.

	Tussen statements keert de stapelwijzer SW in een blok steeds terug tot hetzelfde rustpunt ;
we noemen dit de werkruimtewijzer WW : hij wijst naar de eerste stapelplaats voor de anonyme
tussenresultaten.

	Normaliter hoeft men zich over de WW-waarde van een blok niet te bekommeren. Tijdens de
uitvoering van een statement wordt immers de SW evenveel opgehoogd als afgelaagd en de SW keert
automatisch tot zijn rustpunt terug. We hebben echter ook de zg. "plotselinge blokverlating" :
in een blok kan een "goto L" staan, waarbij "L" een globale label is. Als we hierin terugkeren in
een blok, dat we via een type procedure, dwz. midden in een statement, tijdelijk verlaten hebben,
dan hebben we in het bestemmingsblok als regel nog een paar anonyme tussenresultaten te vergeten,
maw : SW moet teruggezet worden op de waarde van WW, die bij de activering van het
bestemmingsblok behoort.

	Onze gedachten bepalen we even tot binnenblokken. Als we zitten in een binnenblok B van
hoogte n, dan zijn we daarin gekomen via het nauwst lexicographisch omvattende procedureblok
op hoogte m ( m < n ). Bij de binnenkomst in dat procedureblok A hebben we in de stapel een nieuwe
display ingevoerd, waarvan de onderste m elementen uit een andere display gecopieerd zijn
(zie onder), waar het m + 1ste element uit de SW is afgeleid en waarvan de overige elementen
beantwoorden aan de binnenblokken van A. Het idee is, om tijdens de uitvoering van binnenblok B
de locale grootheden van dit blok te localiseren ten opzichte van element n van deze display en
element  n + 1  gelijk te laten zijn aan de bijbehorende waarde van WW. Gaan we een binnenblok
van B in, dan fungeert element  n + 1  onveranderd als referentiepunt voor de locale grootheden
van dit blok en element  n + 2  bergt dan de (binnen-)WW. Dit is de reden, waarom de
binnentophoogte 1 hoger gekozen is dan de maximum voorkomende binnenblokhoogte.

4. Ingaan en uitgaan van binnenblokken.

	Bij het ingaan van een binnenblok op hoogte n en bij het uitgaan moeten we de waarde van n
weten : bij het binnengaan om te weten waar (nl. op plaats  n + 1  van de display) we de nieuwe
WW invullen, bij het verlaten omdat we dan de SW terug moeten zetten, dwz. gelijk moeten maken
aan element n van de heersende display.

	In de programmatekst is de heersende blokhoogte, wat een lexicographisch bepaalde grootheid
is, desgewenst statisch bekend en we kunnen de mechanismen "binnenblok in" en "binnenblok uit"
creeren, zodat ze van het programma een parameter meekrijgen, dwz. "binnenblok in van hoogte n"
en "binnenblok uit van hoogte n".

	Een alternatieve oplossing is, om "ergens" - waarover dadelijk meer - het systeem de heersende
blokhoogte bij te laten houden : "Binnenblok in" en "Binnenblok uit" krijgen dan geen parameter van
het programma mee, maar raadplegen en wijzigen zelf de "ergens" te vinden heersende blokhoogte.
Dit laatste is een techniek, die mij iets meer aanspreekt, hoewel ik er op het moment slechts vage
argumenten ten gunste van weet te bedenken. Het is het algemene argument, dat je in je programma
niet hoeft te vermelden, wat het verwerkende systeem uit de structuur kan afleiden. (Op precies
dezelfde manier als we de waarde van de stapelwijzer niet expliciet aangeven, maar door de
stapelende opdrachten laten meesjouwen.) De tekst van het programma wordt door deze technieken
korter. een nevenvoordeel is, dat de inhoud van de stapel, door de heersende blokhoogte daarin
onder te brengen, sprekender wordt. (Dit is voorlopig ook nog vaag : het zou wel eens gewenst
kunnen zijn, dat we in de stapel een zodanige administratie bijhouden, dat de stapelinhoud op elk
gewenst moment "extern interpretabel" is. Ik denk aan stapelverschuivingen door de coordinator
en post mortem dumps.)

	Als we de heersende blokhoogte willen onthouden, dan rijst de vraag : waar ?

	In de MC1-vertaler deden we dit op een vaste plaats : daar was de heersende blokhoogte
een in enkelvoud aanwezige, plaatsgebonden staturvariabele. Dit zou voor ons onpractisch zijn
in verband met multiprogrammering, omdat we dan bij wisseling van programma de heersende
blokhoogte zouden moeten redden. Als we de heersende blokhoogte als globale variabele van een
programma invoeren, dwz. onder in de stapel van dat programma, dan hebben we de
multiprogrammeringsmoeilijkheid ondervangen, maar zijn we wat betreft de uni-programmering
nog net in de toestand die we bij de MC1-vertaler hebben : redden en herstellen bij procedure
aanroepen en returns. Mijn voorlopige suggestie is, om de heersende blokhoogte op te bergen bij
de heersende display, dwz. als ML[-1]. Deze suggestie is voorlopig, omdat ik nog moet nakijken,
of we door de nog niet in het beeld betrokken parametersituatie niet in moeilijkheden komen.

	De heersende blokhoogte kan dan bij ingaan en uitgaan van binnenblokken bijgehouden
worden ; bij binnenkomst in een procedure, waar we een nieuw display introduceren, moet de
blokhoogte van de procedure bekend zijn (nl. om te weten, hoeveel plaatsen in de nieuwe display
gecopieerd moeten worden) ; bij die gelegenheid kan ook de initialisering van het nieuwe
heersende bloknummer verzorgd worden.

	Ik eindig deze korte notitie met het signaleren van de volgende mogelijke complicaties :

1) bij blokverlating moeten we, als er in dit blok "grote arrays" geintroduceerd waren, de door
deze arrays bezette trommelpagina's weer vrijgegeven worden.

2) bij "plotseling blokverlating" kunnen een heleboel blokken uit de stapel verdwijnen ; wederom
geldt, dat aflagen van SW niet voldoende is, omdat er ook grote arrays hierdoor afgevoerd
kunnen moeten worden.

3) in de parameter-situatie zitten we nu heel anders : we werken dan onder controle van een
heersende L, maar het daarbij geborgen blokhoogte-gegeven ML[-1] heeft op dat ogenblik geen
betekenis. Dit zou zich kunnen wreken, als we er over denken, wat we moeten doen, als de
stapel verschoven moet worden.

								E.W.Dijkstra