6. De programmeertaal PGLE

PGLE is een deeltaal van PGL, gedefinieerd door de beperking dat in een PGLE-programma elke testinstructie wordt gevolgd door een goto-instructie of een terminatie-instructie. Dus bijvoorbeeld 
 +a  en  -a;+b;##L0
zijn wel PGL-programma's, maar geen PGLE-programma's. In het volgende hoofdstuk zal duidelijk worden waarom PGLE een veel prettiger programmeertaal is dan PGL.

Het zal misschien geen verrassing zijn dat elk gedrag dat in PGL programmeerbaar is, ook in PGLE te programmeren is (misschien wel?). Anders gesteld: de beperking tot PGLE is geen beperking in expressieve zin.

Hieronder beschrijven we een transformatie van PGL naar PGLE die van een willekeurig PGL-programma een PGLE-programma met hetzelfde gedrag maakt. Programmatransformatie is een belangrijk onderwerp in de Informatica.

Er is ook een interactieve beschrijving van het volgende: zie de link http://student.science.uva.nl/~sschroev/pga/extra/.

Neem een willekeurig PGL-programma u1;...;uk. Laat het getal m de waarde zijn van het grootste label dat in u1;...;uk voorkomt (dus in een labelinstructie of een goto-instructie) en m=0 als er geen labels voorkomen. We definieren nu een transformatie T door middel van een hulpfunctie t(j,u) die op instructieniveau werkt: 

 T(u1;...;uk) = t(1,u1);...;t(k,uk)
Hier is t(j,u) een hulpfunctie die afhankelijk van de positie j van instructie uj de transformatie precies definieert: 
 t(j,+a) = -a;##Lm+j+1;Lm+j,
 t(j,-a) = +a;##Lm+j+1;Lm+j,
 t(j,u)  = u;Lm+j  anders.
De reden om alle nieuwe label- en goto-instructies met m te verhogen is dat deze dan nooit met de oorspronkelijke kunnen reageren. Bijvoorbeeld in het PGL-programma +a;;##L1;b geldt dat m=1 en 
 T(+a;##L1;b) = t(1,+a);t(2,##L1);t(3,b) = -a;##L3;L2; ##L1;L3; b;L4.
Omdat de transformatie T een afbeelding van PGL naar PGLE is, noemen we deze verder pgl2pgle, waar de 2 verwijst naar het Engelse to. We zullen later meer transformaties met een dergelijke, systematische naamgeving bekijken.

We besluiten met enkele voorbeelden van de transformatie pgl2pgle, waarbij we terwille van de leesbaarheid enkele spaties invoegen: 

 pgl2pgle(b;+a;c) = t(1,b);t(2,+a);t(3,c)
                  = b;L1; -a;##L3;L2; c;L3

 pgl2pgle(L1;+a;b;##L1) = L1;L2; -a;##L4;L3; b;L4; ##L1;L5  (ga na).

Opgaven

Pas de transformatie pgl2pgle toe op de volgende programma's:
  1. L0;-<x==0>;[x=x+1];+<x==0>;!;##L0

  2. +b;d;##L7;-c;a;L7;c
Naar bovenkant pagina