‘Meneer van Dalen voor computers’
Programmeertalen hebben grammatica’s, net als gewone talen. Soms komen daar dubbelzinnigheden in voor. Een computerprogramma dat in die taal is geschreven kan daardoor iets doen wat je niet wilt, het kan fouten maken. Dit soort fouten is heel lastig te vinden en het is ook erg kostbaar om ze te repareren. Bas Basten, promovendus van het Centrum Wiskunde & Informatica (CWI) in Amsterdam, ontwierp nieuwe tools en technieken om zulke ambiguïteiten te vinden. Op 15 december 2011 promoveert hij op zijn proefschrift ‘Ambiguity Detection for Programming Language Grammars’ aan de Universiteit van Amsterdam. Met de nieuwe, op het CWI ontwikkelde technieken zijn grammatica’s voor programmeertalen sneller te controleren op ambiguïteiten – soms tot duizenden keren sneller. Resultaten van dit onderzoek zijn nuttig voor software engineers, bijvoorbeeld bij het ontwerp van domeinspecifieke talen (DSLs).
Meneer Van Dalen
Vroeger hoorden kinderen bij rekenen vaak het – inmiddels in onbruik geraakte
–
ezelsbruggetje ‘Meneer Van Dalen wacht op antwoord’: machtsverheffen gaat vóór
vermenigvuldigen, delen en worteltrekken, en die hebben op hun beurt weer voorrang op optellen
en aftrekken. De som 1+1*3 is volgens de rekenregels gelijk aan 1+(1*3)=4, maar
wie deze regels niet kent, kan ook uitkomen op het antwoord (1+1)*3 = 6. Als
het voor een computer niet duidelijk is welke handeling hij eerst moet doen, dan
kan er 'spraakverwarring' tussen de programmeur en de computer optreden,
waardoor er fouten in de software kunnen ontstaan. Het is daarom belangrijk dat
alle dubbelzinnigheden worden opgelost voordat een taal in gebruik wordt
genomen. Omdat er oneindig veel combinaties van operatoren zoals + en *
bestaan, gebeurt het regelmatig dat makers van nieuwe programmeertalen een
dubbelzinnige combinatie over het hoofd zien bij het ontwerp.
Promovendus Bas Basten onderzocht eerst bestaande methoden om ambiguïteiten in grammatica’s van programmeertalen op te sporen. Daarna ontwikkelde hij eigen, verbeterde technieken. Zo ontwierp hij een methode en de bijbehorende tool AmbiDexter, die eerst stukken grammatica zonder ambiguïteiten wegfiltert. Daardoor kan de rest sneller doorzocht worden op dubbelzinnigheden. Als een ambiguïteit eenmaal gevonden is, is het vaak erg moeilijk om te zien wát er precies mis is. Daarom ontwikkelde Basten met zijn collega’s ook het expertsysteem ‘Dr. Ambiguity’, dat de oorzaak van de dubbelzinnigheid analyseert. Beide tools zijn geïntegreerd met Rascal, de meta-programmeertaal van het CWI. Ze zijn gratis (open source) beschikbaar gesteld aan gebruikers. In een praktijkcase bleken er in verschillende grammatica’s van programmeertalen ambiguïteiten te zitten. AmbiDexter is een van de eerste bruikbare detectiesystemen voor ambiguïteiten in software en de snelste. Uit benchmarks blijkt dat de methode door het filteren zelfs tot duizenden keren sneller kan zijn. Dit onderzoek is een goed voorbeeld van ‘Software als Service’ – een van de speerpunten van het CWI.
Meer informatie: http://homepages.cwi.nl/~basten/ambiguity/
en http://www.rascal-mpl.org/.
Promotor: prof. dr. Paul Klint (CWI en UvA), copromotor: dr. Jurgen J. Vinju (CWI).
Promotie: 15 december 2011, Agnietenkapel, Oudezijds Voorburgwal 231, Amsterdam. 14.00 uur.
Zie ook: http://www.student.uva.nl/se/announcements.cfm/048F4E50-0729-4FA1-AAE62FF457F77AAA
Illustratie: Ambigram, door Bas Basten (CWI).
