10 Objectgebaseerd Programmeren
10.1 Random: Willekeurige getallen genereren
Deze oefening is gebaseerd op onder andere oefening 3.6 van Structure and Interpretation of Computer Programs
10.1.1 Simpele generator
Schrijf een procedure (make-random m a seed) die men kan gebruiken om onafhankelijke generatoren van willekeurige (random) getallen te creëren. De random getallen worden gegenereerd met de volgende reeks:
\[x_{i + 1} = (x_i * a) \mod m\]
Waarbij \(x_0 = seed\) (goede waarden voor m en a zijn \(m = 2^{32} -1\) en \(a = 7^5\)). Om de gewenste output te bekomen moet je enkel nog \(\frac{x_i}{m}\) uitwerken zodat je een getal tussen 0 en 1 bekomt.
> (define random (make-random (- (expt 2 32) 1) (expt 7 5) 97)) > (random) 0.0003795789089937645
> (random) 0.3795827234582004
> (random) 0.646833161974054
10.1.2 Generator met berichten
Pas de procedure make-random aan zodanig dat het mogelijk is om de random generator te resetten. Indien bijvoorbeeld random een random-generator is die gedefinieerd is m.b.v. make-random, dan produceert ((random 'generate)) een nieuw random getal, en ((random 'reset) new-seed) zet de interne variabele op de waarde new-seed.
> (define random (make-random (- (expt 2 32) 1) (expt 7 5) 99)) > ((random 'generate)) 0.0003874052782513679
> ((random 'generate)) 0.5111205115707406
> ((random 'generate)) 0.40243796943743665
> ((random 'reset) 99) > ((random 'generate)) 0.0003874052782513679
> ((random 'generate)) 0.5111205115707406
> ((random 'generate)) 0.40243796943743665
10.2 Examen Wiskunde Partieel januari 1995
Eufrasie is dolgelukkig. Ze is er net in geslaagd haar eerste "object met toestand" in Scheme aan de praat te krijgen. Ze heeft meer bepaald een counter object gemaakt dat reageert op de boodschappen increase! (1 ophogen), decrease! (1 verlagen) en read (waarde uitlezen). Haar code is correct en ziet er als volgt uit:
(define (make-counter initial) (define (increase!) (set! initial (+ initial 1))) (define (decrease!) (set! initial (- initial 1))) (define (dispatch m) (cond ((eq? m 'increase!) increase!) ((eq? m 'decrease!) decrease!) ((eq? m 'read) initial) (else (display "wrong message")))) dispatch)
Nu wil Eufrasie een counter object gebruiken om een simulatie van een parking met 2 verdiepen te implementeren. Elk verdiep heeft een zekere capaciteit. De verdiepen worden in volgorde opgevuld, m.a.w. als een bepaald verdiep vol zit (leeg is) moet naar het bovenliggende (onderliggende) verdiep (indien er nog een is) worden overgegaan. Zo’n parkeergarage wordt als volgt aangemaakt: (define parkeergarage (make-parking capacity1 capacity2))
en verstaat de volgende boodschappen:
(parkeergarage 'full?): is de garage vol?
(parkeergarage 'empty?): is de garage leeg?
(parkeergarage 'level): geeft het nummer van het verdiep (1 of 2) dat momenteel wordt opgevuld
((parkeergarage 'car-enters!)): #f indien de garage vol is. In het andere geval wordt de teller van 1 der verdiepen met 1 vermeerderd.
((parkeergarage 'car-leaves!)): #f indien de garage leeg is. In het andere geval wordt de teller van 1 der verdiepen met 1 verminderd.
Implementeer make-parking die een parking aanmaakt waarbij de aantallen worden bijgehouden door counter-objecten zoals hierboven gedefinieerd (dus zonder de code uit make-counter opnieuw op te schrijven).
> (define parking (make-parking 3 5)) > (parking 'level) 1
> (parking 'full?) #f
> ((parking 'car-enters!)) > ((parking 'car-enters!)) > ((parking 'car-enters!)) > ((parking 'car-enters!)) > (parking 'level) 2
> (parking 'empty?) #f
> ((parking 'car-enters!)) > ((parking 'car-enters!)) > ((parking 'car-enters!)) > ((parking 'car-enters!)) > (parking 'full?) #t
> ((parking 'car-enters!)) #f
> ((parking 'car-leaves!)) > ((parking 'car-leaves!)) > ((parking 'car-leaves!)) > ((parking 'car-leaves!)) > ((parking 'car-leaves!)) > ((parking 'car-leaves!)) > (parking 'level) 1
10.3 Examen januari 2018: Laadpark
Voor deze oefening is het de bedoeling dat je laadparken voor elektrische auto’s implementeert als objecten. Een laadpark bestaat uit 1 of meerdere laadstations aan welke een elektrische auto gekoppeld kan worden. Deze auto kan het station dan gebruiken om zijn batterij op te laden. Het eerste deel van de vraag bestaat er uit om objecten voor auto’s, laadstations, en laadparken te implementeren. Voor het tweede deel moet je code schrijven waarmee je het gebruik van de objecten illustreert.
10.3.1 Laadstation
Implementeer het ADT laadstation m.b.v. objecten zoals gezien in het hoofdstuk over single-dispatch OOP.
ADT laadstation maak-laadstation ( ∅ -> laadstation ) withdraw! ( laadstation number -> ∅ ) koppel! ( laadstation auto -> ∅ ) ontkoppel! ( laadstation -> ∅ ) vrij? ( laadstation -> boolean )
Een laadstation weet op elk moment of het gekoppeld is aan een auto of niet, en hoeveel elektriciteit er in totaal al afgenomen is.
Een laadstation moet je kunnen aanmaken met (maak-laadstation). Een laadstation moet minstens deze boodschappen begrijpen:
De boodschap withdraw! zal een gegeven hoeveelheid stroom van het laadstation afnemen.
De boodschap koppel! zal een wagen koppelen aan het laadstation.
De boodschap ontkoppel! zal de wagen ontkoppelen van het laadstation.
De boodschap vrij? zal teruggeven of het station al dan niet aan een auto gekoppeld is.
10.3.2 Auto
Implementeer het ADT auto m.b.v. objecten zoals gezien in het hoofdstuk over single-dispatch OOP.
ADT auto maak-auto ( number -> auto) charge ( auto -> number ) charge! ( auto -> ∅ ) koppel! ( auto laadstation -> ∅ ) ontkoppel! ( auto -> ∅ )
Een auto heeft een batterij met een vaste capaciteit, gegeven in kilowattuur. Een auto weet hoeveel procent de batterij nog opgeladen is, en of hij al dan niet gekoppeld is aan een laadstation. Als de auto gekoppeld is aan een laadstation, kan de auto electriciteit, opnieuw gegeven in kilowattuur, onttrekken van dit station om de batterij terug op te laden.
Het koppelen en ontkoppelen van een auto aan een laadstation wordt altijd geinitieerd door een auto!
Een auto moet je kunnen aanmaken met (maak-auto capaciteit). Een capaciteit wordt dus meegegeven in de constructor. Een auto moet minstens deze boodschappen begrijpen:
De boodschap charge geeft terug hoeveel procent de auto opgeladen is.
De boodschap charge! zal de auto volledig opladen, als die aan een laadstation gekoppeld is.
De boodschap koppel! neemt een laadstation als argument en koppelt de auto er aan.
De boodschap ontkoppel! zal de auto ontkoppelen van het laadstation.
> (define mijn-auto (maak-auto 70))
> (mijn-auto 'charge) 100
10.3.3 Laadpark
Implementeer het ADT laadpark m.b.v. objecten zoals gezien in het hoofdstuk over single-dispatch OOP.
ADT laadpark maak-laadpark ( number -> laadpark ) full? ( laadpark -> boolean ) enter! ( laadpark auto -> boolean )
Een laadpark beheert n laadstations. Bij het aanmaken van een laadpark worden de bijhorende laadstations automatisch aangemaakt. Men kan gebruik maken van een laadpark door een auto het park te laten betreden. Bij het betreden van het laadpark, zal het laadpark de auto automatisch koppelen aan een vrij laadstation. Als er geen laadstation vrij is om de auto aan te koppelen, zal de enter! boodschap #f teruggeven, anders geeft enter! #t terug.
Een laadpark moet je kunnen aanmaken met (maak-laadpark n). Het aantal laadstations n wordt dus meegegeven in de constructor. Een laadpark moet minstens deze boodschappen begrijpen:
De boodschap full? zal teruggeven of het laadpark volzet is.
De boodschap enter! kan gebruikt worden om een auto het laadpark te laten betreden.
10.3.4 Gebruik van de objecten
Schrijf nu een scenario uit waarbij je een laadpark van grootte 2, en 3 auto’s aanmaakt (capaciteit maakt niet uit). Probeer alle 3 auto’s aan het laadpark te koppelen, deze op te laden, en 1 van de auto’s daarna te ontkoppelen.
10.4 Extra Oefeningen
10.4.1 Make-withdraw
In de make-withdraw procedure uit het boek wordt de interne variabele balance gecreëerd als een parameter van make-withdraw. Het is ook mogelijk om dergelijke interne variabelen expliciet te creëren met een let.
(define (make-withdraw initial-amount) (let ((balance initial-amount)) (lambda (amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds"))))
Gebruik omgevingsmodel-diagrammen om deze versie van make-withdraw te analyseren. Bespreek de verschillen met de versie uit het boek.
10.4.2 ADT’s en objecten
Geef object-georiënteerde implementaties van de ADT’s uit de reeks over Lijsten. Voor ADT Point, implementeer de constructor (make-point x y). Een point moet de volgende berichten begrijpen:
'x-value
'y-value
Voor ADT Segment (of lijnstuk), implementeer de constructor (make-segment start end). Een Segment moet de volgende berichten begrijpen:
'start-point
'end-point
'mid-point
Voor ADT Vector, implementeer de constructor (make-w-vector . args). Een vector moet de volgende berichten begrijpen:
'dimension
'coordinate
'add
Voor ADT Polynome, implementeer de constructor (make-polynome . coefficients). Een polynome moet de volgende berichten begrijpen:
'order
'coefficients
> (define point1 (make-point 6 10)) > (define point2 (make-point 10 20)) > point1 #<procedure>
> (point1 'x-value) 6
> (define segment (make-segment point1 point2)) > segment #<procedure>
> (segment 'start-point) #<procedure>
> ((segment 'start-point) 'y-value) 10
> (define midpoint (segment 'midpoint)) > midpoint #<procedure>
> (midpoint 'x-value) 8
> (define w-vector1 (make-w-vector 1 2 3)) > (define w-vector2 (make-w-vector 4 5 6)) > ((w-vector1 'coordinate) 2) 2
> ((w-vector2 'coordinate) 1) 4
> ((w-vector1 'add) w-vector2) #<procedure>
> ((((w-vector1 'add) w-vector2) 'coordinate) 1) 5
> (define polynome (make-polynome 1 2 3)) > (polynome 'order) 2
> ((polynome 'coefficient) 2) 2
10.4.3 Examen Informatica 1eZit 1994
10.4.3.1 Omgevingsmodel-diagram
Teken een omgevingsmodel-diagram voor de situatie na evaluatie van het volgend stuk Scheme code:
(define (subtract-ct n c) (set! n (- n c)) n) (define (make-sub i) (lambda (p) (subtract-ct p i))) (define sub1 (make-sub 1)) (define x 5)
10.4.3.2 Verklaar
Wat is het resultaat van de evaluatie van de volgende expressies? Verklaar je antwoord aan de hand van omgevingsmodel-diagrammen.
(sub1 x)
x
10.4.4 Examen Informatica 1eZit 1995
Gegeven de volgende definities
(define hulp 2) (define (haha x) (let ((hulp (* x hulp))) (display hulp)) (display hulp) (set! hulp 4))
Voorspel dan de output van de volgende expressies aan de hand van omgevingsmodel-diagrammen.
(haha 2)
(haha 3)
10.4.5 Examen Informatica 2eZit 1994
Gegeven de volgende definities:
(define a 2) (define b 4) (define (foo a) (let ((a (* a b)) (b (+ a b))) (display b) (set! a 3) (set! b 3) (display a)))
Teken de omgevingsmodel-diagrammen voor de evaluatie van (foo 1). Wat zal er uiteindelijk op het scherm worden afgedrukt? Wat zijn de waarden van de globale variabelen a en b na afloop?
(foo 1)
10.4.6 Examen Informatica 2eZit 1997
Gegeven de volgende definities:
(define a 2) (define b 4) (define (foo bar a) (let* ((a (bar a b)) (b (bar a b))) (display b)) (set! a 3) (set! b 3) (display a))
10.4.6.1 Omgevingsmodel-diagrammen
Teken de omgevingsmodel-diagrammen voor de evaluatie van (foo + 1) en (foo * 2) indien deze na elkaar geëvalueerd worden. Welke getallen zullen uiteindelijk op het scherm worden afgedrukt?
(foo + 1)
(foo * 2)
10.4.6.2 Voorspel
Wat gebeurt er als je vervolgens (foo 2 4) evalueert?
(foo 2 4)
10.4.7 Examen Informatica Partieel januari 1995
Frank is dolgelukkig. Hij is er zopas in geslaagd zijn eerste "object met toestand" in Scheme aan de praat te krijgen. Hij heeft meer bepaald een counter object gemaakt dat reageert op de boodschappen reset (op 0 zetten), next (1 ophogen) en read (waarde uitlezen).
Frank’s volgende opdracht is nu om een object scorebord te maken voor de plaatselijke basketbalvereniging. Dit is een object dat de score bijhoudt van de thuisploeg en de bezoekersploeg en dat slechts reageert op de boodschappen reset (beide scores op 0 zetten), read (beide scores uitlezen) en score (de score van 1 van de 2 ploegen verhogen met 1, 2 of 3 punten).
Frank is echter zo fier op zijn eerste creatie dat hij ze kost wat kost wil hergebruiken. I.h.b. wil hij dus proberen om binnenin zijn scorebord twee counter objecten te gebruiken die de score van elk van de ploegen bijhouden.
10.4.7.1 Implementeer
Schrijf het geheel uit. Implementeer eerst de counter, met als constructor een procedure make-counter.
Een counter moet, zoals hiervoor vermeld, de volgende berichten begrijpen:
'reset
'next
'read
Implementeer dan een scorebord object, met als constructor een procedure make-scorebord. Een scorebord moet intern twee counter objecten bijhouden, één voor elk ploeg.
Een scorebord moet, zoals hiervoor vermeld, de volgende berichten begrijpen:
'reset
'read
'score
10.4.7.2 Manipuleer
Laat zien hoe je een scorebord object aanmaakt en hoe je het manipuleert.
10.4.8 Objecten en het omgevingsmodel
Laurent vindt in een software-bibliotheek een procedure om "rechthoek"-objecten te maken:
(define (maak-rechthoek l b) (define (oppervlakte) (* l b)) (define (omtrek) (* 2 (+ l b))) (define (dispatch m) (cond ((eq? m 'oppervlakte) (oppervlakte)) ((eq? m 'omtrek) (omtrek)))) dispatch)
Hij moet als oefening een object vierkant aanmaken dat herschaalbaar is. Hij herinnert zich dat een vierkant een rechthoek is met vier gelijke zijden en bedenkt daarom de volgende oplossing:
(define (maak-vierkant zijde) (define rechthoek (maak-rechthoek zijde zijde)) (define (schaal! n) (set! zijde (* n zijde))) (define (dispatch m) (cond ((eq? m 'oppervlakte) (rechthoek 'oppervlakte)) ((eq? m 'omtrek) (rechthoek 'omtrek)) ((eq? m 'schaal!) schaal!))) dispatch)
> (define test (maak-vierkant 5)) > (test 'oppervlakte) 25
> (test 'omtrek) 20
> ((test 'schaal!) 2) > (test 'oppervlakte) 25
Hoe komt dit? Teken zorgvuldig omgevingsmodellen die uitleggen wat er gebeurt bij de aanmaak van het vierkant, bij de vraag om de oppervlakte te berekenen, en bij de vraag om te schalen. Leg dan met een paar zinnen uit waarom het antwoord op de laatste vraag 25 is i.p.v. 100.
10.4.9 Examen Informatica Partieel januari 1996
Een gloeilamp heeft slechts 3 mogelijke toestanden: "aan", "uit" of "kapot". Initieel is een gloeilamp steeds "uit". Elke gloeilamp gaat na een bepaalde tijd kapot. Voor gloeilampjes in een kerstboom wordt deze tijd voornamelijk bepaald door het aantal ker dat het lampje al aan en uit is gegaan. Het lampje kan nadat het kapot is gegaan wel vervangen worden en gaat vanzelf dan weer een bepaalde tijd mee.
Schrijf een Scheme-procedure (MaakLampje aantal) die dergelijke gloeilampjes aanmaakt. De parameter aantal die moet meegegeven worden bepaalt het aantal keer dat het lampje van toestand kan veranderen alvorens kapot te gaan. Een gloeilamp aangemaakt door deze procedure is een object dat de volgende boodschappen moet verstaan:
switch! Verandert de toestand van de gloeilamp van "aan" naar "uit" of omgekeerd. Geeft na afloop #t terug indien het lampje nog steeds niet kapot is, anders #f.
on? Geeft #t indien de gloeilamp "aan" is, zoniet #f.
off? Geeft #t indien de gloeilamp "uit" is, zoniet #f.
test? Geeft #t indien de gloeilamp "kapot" is, zoniet #f.
change! Vervangt de gloeilamp zodat ze weer een aantal keer aan en uit kan gaan. Deze tijd wordt bepaald door een parameter nieuwAantal die als argument moet worden meegegeven aan de boodschap. Na afloop wordt het symbool 'changed teruggegeven.
10.4.10 Examen januari 2003: Object vraag
Ontwerp 2 ADT’s die je als object implementeert.
10.4.10.1 Tel-object
((teller 'toets) bedrag): bedrag wordt ingetoetst in het tel-object en opgeteld bij het huidige bedrag.
(teller 'lees): geeft het huidige bedrag.
(teller 'reset): het huidige bedrag wordt op nul gezet.
10.4.10.2 Winkelkassa
((winkelkassa 'toets) bedrag): een bedrag wordt ingetoetst in de kassa, dit kan zowel voor de kostprijs van 1 artikel zijn, als voor het intoetsen van geld dat de klant overhandigt. Let wel het intoetsen van het overhandigde bedrag kan pas gebeuren als de totale kostprijs werd afgelosten m.b.v. de enter message.
(winkelkassa 'enter): afhankelijk van wat werd ingetoetst reageert de kassa als volgt: wanneer de prijs van het laatste artikel werd ingetoetst, wordt het totale bedrag dat de klant moet betalen afgesloten en teruggegeven, wanneer het bedrag werd ingetoetst dat de klant overhandigt dan wordt het wisselgeld berekend, het saldo van de kassa wordt verhoogd met het verschuldigde bedrag, het verschuldigde bedrag wordt gereset op nul en uiteindelijk wordt het wisselgeld teruggegeven.
(winkelkassa 'inhoud): het huidige saldo van de kassa wordt opgevraagd.
(winkelkassa 'afsluiten): het huidige saldo van de kassa wordt teruggegeven en op nul gereset.
Laat door middel van een klein transcriptje zien hoe je een winkelkassa aanmaakt en gebruikt.
10.4.11 Examen januari 2004: Object vraag
10.4.11.1 Buffer
newValue: voegt een nieuwe waarde toe aan de buffer.
return: geeft de inhoud van de buffer terug.
returnSum: geeft de som van alle getallen die in de buffer zijn opgeslagen terug.
flush: maakt de buffer leeg.
Implementeer het object buffer, aangemaakt met (maak-buffer), dat dit gedrag kan voorstellen.
10.4.11.2 Verkeersteller
newCar: voor elke auto die langs de verkeersteller rijdt wordt deze boodschap gestuurd, er wordt een tellertje opgehoogd dat het aantal voorbijgereden auto’s bijhoudt.
newHour: op elk volledig uur wordt dit bericht naar de verkeersteller gestuurd, de teller wordt uitgeschreven naar een buffer en de teller wordt weer op nul gezet.
newDay: op het einde van de dag (na 24 uur) wordt dit bericht naar de verkeersteller gestuurd, er wordt een overzicht gegeven van de dag (aantal auto’s die voorbijgereden zijn + het drukste uur, d.w.z. het uur zelf en het aantal auto’s dat er in dat uur voorbijgereden zijn). Tenslotte wordt de buffer leeggemaakt en de teller op nul gezet voor de volgende dag.
Implementeer het object verkeersteller, aangemaakt met (maak-verkeersteller), dat dit gedrag kan voorstellen. Maak hierbij gebruik van een counter object (dat de boodschappen increment, read en reset verstaat) en het buffer object.
10.4.12 Twitter
We willen een eenvoudige Twitter applicatie schrijven waarbij gebruikers een account kunnen aanmaken en gebruikers elkaar kunnen volgen. Een account laat uiteraard toe om tweets te verzenden, die dan door al de volgers kunnen gelezen worden.
10.4.12.1 Tweet
Ontwerp een ADT Tweet dat je als object implementeert. Een tweet onthoudt de gebruikersnaam van de persoon die het bericht getweet heeft, alsook de mogelijks bijhorende tags. Wanneer het bericht uit meer dan 140 karakters bestaat, wordt er #f teruggegeven (je kan de procedure string-length gebruiken om de lengte van een string na te gaan). Een tweet maak je aan door de constructor make-tweet op te roepen. Een tweet moet minstens deze vier boodschappen begrijpen:
De boodschap username geeft de gebruikersnaam van de persoon die de tweet getweet heeft.
De boodschap text geeft de tekst terug.
De boodschap tags geeft de tags die bij de tweet horen terug.
De boodschap display geeft de tweet weer op het scherm.
> (define my-tweet (make-tweet "madewael" "Racket is cool!" (list "#Racket" "#Scheme")))
> (my-tweet 'username) "madewael"
> ((my-tweet 'display))
Tweet from madewael
Racket is cool!
Tags: #Racket #Scheme
10.4.12.2 Account
Ontwerp een ADT account dat je als object implementeert. Een account onthoudt een gebruikersnaam en de naam van de persoon die de account aanmaakt. Verder onthoudt een account ook zijn followers (accounts van personen die hem volgen), de berichten die hij getweet heeft (tweets) en de tweets van zowel hemzelf als alle accounts die hijzelf volgt (tweet-wall). Een account maak je aan door de constructor make-account op te roepen. Een account moet minstens deze zeven boodschappen begrijpen:
De boodschap username geeft de gebruikersnaam terug.
De boodschap name geeft de naam terug.
De boodschap follow waarbij deze account zichzelf registreert als volger van een andere account.
De boodschap add-follower die een account toevoegt aan de volgers van deze account.
De boodschap tweet die gegeven tekst en tags een tweet aanmaakt en deze toevoegt aan de tweets van deze account. Hierbij wordt deze tweet ook toegevoegd aan de tweet-wall van de accounts die deze account volgen (de accounts die worden bijgehouden in followers).
De boodschap add-tweet-to-wall waarbij een tweet wordt toegevoegd aan de tweet-wall.
De boodschap display die ofwel de followers, tweet-wall of de volledige account weergeeft op het scherm.
> (define accountE (make-account "Eline Philips" "ephilips"))
> (define accountM (make-account "Mattias De Wael" "madewael"))
> ((accountE 'follow) accountM)
> ((accountM 'tweet) "Racket is cool!" "#Racket" "#Scheme")
> ((accountE 'tweet) "Hello World!")
> ((accountE 'display) 'account)
Twitter name ephilips
Name Eline Philips
TWEET WALL
Tweet from ephilips
Hello World!
Tags:
Tweet from madewael
Racket is cool!
Tags: #Racket #Scheme
FOLLOWERS
> ((accountM 'display) 'account)
Twitter name madewael
Name Mattias De Wael
TWEET WALL
Tweet from madewael
Racket is cool!
Tags: #Racket #Scheme
FOLLOWERS
ephilips