de samenvatting (PDF)

Efficient Abstractions for Visualization and Interaction
A.J. van der Ploeg
Samenvatting:
Een belangrijk instrument voor elke programmeur is het gebruik van abstracties, zoals functies en
methoden. Abstracties verbergen de details van een berekening, zodat de programmeur alleen maar
hoeft te weten wat een abstractie berekent, niet hoe de berekening er in detail uitziet. Het gebruik
van abstracties kan echter het ongewenste effect hebben dat het resulterende programma niet
efficient genoeg is. Om voldoende efficiëntie te bereiken gaan programmeurs sommige abstracties
vermijden en in plaats daarvan de gewenste functionaliteit van de grond af aan opbouwen.
Het doel van dit proefschrift is om abstracties voor interactieve visualisaties efficiënter te maken. Ik
zal me daarbij richten op efficiëntere abstracties voor het maken van twee-dimensionale beelden,
layouts van bomen en interactiviteit.
* Abstracties voor het maken van twee-dimensionale beelden
Abstracties voor het maken van twee-dimensionale beelden, zoals het tekenen van een lijn, het
inkleuren van een vorm of het roteren van een tekening, zijn belangrijke gereedschappen bij het
programmeren van interactieve visualisaties. Ik presenteer een verzameling nieuwe declaratieve
abstracties voor het maken van resolutieonafhankelijke, twee-dimensionale beelden, die het
makkelijker maken om een hoge beeldkwaliteit te bereiken en ervoor zorgen dat niet-affiene
transformaties direct uitdrukbaar en efficient zijn. Als voorbeeld laat ik zien dat het programmeren
van een lokale vergroting, de zogenaamde focus+context lens, met deze nieuwe abstracties een
betere beeldkwaliteit geeft, efficiënter is, en minder code vergt dan een implementatie van dezelfde
vergroting met bestaande abstracties.
* Abstracties voor layouts van bomen
Interactieve visualisaties zijn vaak
gebaseerd op een layout van een boomstructuur. Voor het berekenen van de layout van bomen
bestaat er een klassiek algoritme waarbij het benodigde aantal stappen lineair is in de grootte van de
boom. In sommige gevallen produceert dit algoritme echter een layout die meer oppervlakte
inneemt dan noodzakelijk. Ik presenteer een aanpassing van dit algoritme die voor een compactere
layout zorgt, en bewijs dat het algoritme met deze aanpassing dezelfde tijdscomplexiteit heeft.
* Abstracties voor interactiviteit
Interactieve visualisaties moeten reageren op gebeurtenissen, zoals het drukken op een muisknop of
het ontvangen van een netwerkbericht. De gebeurtenissen worden afgehandeld door `of een
methode aan te roepen die wacht totdat de gevraagde gebeurtenis voorbij is (blocking I/O) of een
methode te installeren die wordt aangeroepen als de gebeurtenis optreedt (een callback). De eerste
methode heeft als nadeel dat het alleen mogelijk is om interactieve programma-onderdelen samen
te stellen door middel van parallellisme, wat de complexiteit van het programma aanzienlijk
verhoogt. De tweede methode heeft als nadeel dat het leidt tot omkering van de besturing
(inversion of control):
de besturingsstroom (control flow) van het programma wordt bepaald door de gebeurtenissen die
optreden, in plaats van door de volgorde van de methodeaanroepen die de programmeur heeft
aangegeven. Dit maakt het moeilijk om het overzicht te houden.
Een alternatieve aanpak voor het afhandelen van gebeurtenissen die niet leidt tot non-determinisme
of omkering van de besturing is Functioneel Reactief Programmeren (FRP). Het gebruik van FRP gaat
echter vaak ten koste van de efficiëntie doordat berekeningen onnodig herhaald worden. Ik
presenteer een nieuw FRP raamwerk, genaamd Monadic FRP, dat incrementeel te werk gaat, en dus
het onnodig herhalen van berekeningen voorkomt.
Een algemeen probleem, dat ook voorkomt in Monadic FRP, is dat voor sommige associatieve
operatoren het aantal stappen dat nodig is om de uitkomst van een expressie te berekenen afhangt
van van de plaatsing van de haakjes, ook al maakt dit voor de uitkomst niet uit. Een oplossing
hiervoor is het gebruik van continuation passing style, maar dit is alleen efficient als de berekening
niet afwisselt tussen het gebruik van de associatieve operator en het observeren van zijn resultaten.
Ik presenteer een oplossing die ook in dit geval een snelheidswinst oplevert, zodat het voor alle
associatieve operatoren qua efficiëntie niet uitmaakt hoe de haakjes geplaatst zijn.
Het is kortom mogelijk om interactieve visualisaties te maken door ze samen te stellen uit simpele
abstracties, zonder dat dit resulteert in een te traag programma.

Download Report