13. Rekenen zonder getallen
Ofschoon onze op MPP gebaseerde programmeertalen geen getallen kennen, kunnen we een vorm van rekenkunde introduceren door getallen te modelleren. We zullen in deze paragraaf twee modellen voor de natuurlijke getallen {0,1,2,3,...} de revue laten passeren. In beide modellen representeren we de natuurlijke getallen als een lijn waarbij ieder getal met een s-veld ("s" voor successor) naar zijn opvolger verwijst en - met uitzondering van de 0 - met een p-veld ("p" voor predecessor) naar zijn voorganger. We spreken af dat het atoom in focus Z de 0 representeert, dat de argumenten van de één-plaatsige functies pred en succ de focusnaam x hebben en dat het resultaat y heet. Het eerste model bestaat uit de PGLEc.mpp-programma's
setZero = Z=new; y=Z
pred = -x/p{; y=x ;}{; y=x.p; }
succ = -x/s{; x.+s; y=new; y.+p ;y.p=x; x.s=y;
}{; y=x.s; }
De benaming voor deze programma's beschrijft hun functionaliteit:
setZero creëert de 0,
pred berekent de voorganger en succ de opvolger.
De molecule die door het programma
wordt gegenereerd, wordt door setZero; x=y; succ; x=y; succ berekend. Hier representeert x de 1 en y de 2. In dit model kunnen we optelling en de "modulus 2"-functie - i.e., de functie die de rest bij geheeltallige deling door 2 berekent - op de volgende manier implementeren:
add = L0; +x2==Z{;y=x1;
}{; x=x1; succ; x1=y; x=x2; pred;
x2=y; ##L0 ;}
mod2 = y=x; L1; -y==Z{; x=y; pred;
-y==Z{; x=y; pred; ##L1; }{; y=x; };
}{; }
In het geval van twee-plaatsige functies zoals add spreken we weer af dat de argumenten x1 en x2
heten en het resultaat y.
Merk op dat de implementaties van deze functies corresponderen met recursieve definities - i.e., definities die zichzelf aanroepen. Zo kunnen we optelling recursief op de volgende manier definiëren:
x1 + x2 = x1 als x2 = 0 en x1 + x2 = (x1+1) + (x2-1) anders.
Hier wordt in de tweede vergelijking het tweede argument stapsgewijs gereduceerd tot 0; het resultaat van de optelling staat dan in het eerste argument. Op een vergelijkbare manier kunnen we de modulus definiëren:
x mod 2 = 0 als x = 0, x mod 2 = (x-2) mod 2 als x-1 > 0 en x mod 2 = x anders.
Programma
laat zien hoe - uitgaande van de getallen 1 (in focus x) en 2 (in focus y) - de som van deze getallen en vervolgens modulus 2 van de som wordt berekend. Na afloop bevindt het resultaat zich in focus y.
Opgaven - inleveren voor 25 november 2011, 22:00 via floris.webklas@gmail.com
Gelieve je antwoorden in Word-formaat in te leveren (zowel doc
als docx mag), met de volgende naamgeving:
Webklas_achternaam_voornaam_weeknummer.doc
Voorbeeld: Webklas_Kroon_Floris_4.doc
-
Merk op dat het algoritme voor de modulus-functie in feite beslist of
een gegeven getal even of oneven is: immers is de modulus van even getallen 0 en van oneven getallen
is dat 1. Dit geeft aanleiding tot een eenvoudig
herontwerp van ons model: we zullen aan ieder getal een reflexief veld toekennen
dat aangeeft of het getal even dan wel oneven is. De modulus-functie kan dan
efficiënter worden geïmplementeerd.
Het setZero programma voor ons nieuw model heeft nu de gedaante
setZero = Z=new; Z.+even; y=Z
Aan het pred-programma hoeven we niets te veranderen maar in succ moet het nieuwe getal nog van een even of oneven veld worden voorzien. Geef deze nieuwe implementatie. - Schrijf een eenvoudig programmaatje voor de modulus 2 in ons nieuwe model.
Naar bovenkant pagina