XML generiek programmeren

Website:website containing additional information
Course code:WIXML
Credits:5.72 ECTS (=4 old credit points)
Period:periode 4 (week 11 t/m 18, dwz 11-3-2002 t/m 3-5-2002; herkansing week 33)
Participants:up till now 10 subscriptions
Schedule:Dit is een oud rooster!
formgrouptimeweekroomteacher
college   ma 15-1711-13 Lang-F127 Johan Jeuring
Andres Löh
    
15-17 BBL-513
do 09-1111-13 Lang-E044
14-17 BBL-513
Contents:Software werkt meestal met gestructureerde informatie; denk bijvoorbeeld aan Web-browsers en HTML-documenten. Die structuur is in wezen een datatype of een DTD (Document Type Definition). Als dat type verandert moeten alle programma's die ermee werken worden aangepast, hoewel meestal de kern van het probleem daar los van staat.

In dit vak worden methoden aangeboden waarmee problemen voor willekeurige DTD's geformuleerd en opgelost kunnen worden. Het resultaat is dan een generiek programma. Een goed voorbeeld is pattern matching, dus het probleem de voorkomens van een patroon in een gegeven data structuur te vinden. Dit is een probleem dat vooral bekend is voor strings, maar het is even belangrijk voor bomen of matrices. Door dat te specialiseren voor een gegeven type krijgen we een gewoon, type-specifiek programma. Design patterns zijn ook een soort generieke programma's.

In het college behandelen we methoden om generiek te programmeren aan de hand van een aantal voorbeeld-problemen. Je leert daarbij ook wat elementaire categorietheorie, wat je een eenvoudig hulpmiddel geeft om over generieke specificaties te redeneren. Verder maken we kennis met de programmeertaal Generic Haskell, een uitbreiding van Haskell voor generiek programmeren. We zullen de aangeboden methoden vooral toepassen op XML-gerelateerde problemen.

Literature:R. Backhouse, P. Jansson, J. Jeuring, and L. Meertens: Generic Programming, An Introduction. In S. Doaitse Swierstra et al (eds): Advanced Functional Programming, LNCS 1608, pages 28--115, Springer-Verlag, 1999. (verkrijgbaar via de www-pagina van dit vak)
Course form:hoorcollege/werkgroepen.
Exam form:inleveropdracht(en).
Minimum effort to qualify for 2nd chance exam:Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.
Description:In dit vak wordt een op categorietheorie gebaseerde manier van programmeren behandeld. Belangrijke begrippen zijn: homomorfismen, functoren, algebra's, initiële algebra's, maps, catamorfismen.

Daarnaast wordt behandeld hoe deze abstracte begrippen gebruikt kunnen worden om programma's voor meer concrete problemen zoals die voorkomen in de XML wereld (data conversie, data opslag, gestructureerde editors), en problemen als unificatie en rewriting automatisch af te leiden voor grote klassen van datatypen. Daarbij wordt Generic Haskell, een uitbreiding van de functionele programmeertaal Haskell, gebruikt.

Kennisdoelen: functoren en hun relatie tot datatypen, (initiële) algebra's, catamorfismen, fusie. Compositioneel programmeren met functoren, maps, catamorfismen, zips, XML/DTD. Casus: een XML tool.

Vaardigheden: Het kunnen herkennen van datatype-onafhankelijke problemen. Het kunnen schrijven van datatype onafhankelijke programma's. Het belang begrijpen van het gebruik van types in het schrijven van generieke programma's.

Inzichtdoelen: Het begrip structuur en abstractie over structuur komt op veel plaatsen binnen de informatica voor: in databases, compilers, editors, etc. Dit hebben de studenten onder andere bij GO en IPT gezien, en dit vak geeft de achtergronden voor het abstraheren over structuur.

Indeling: 1e gedeelte:

  • XML en DTD's
  • Algebra's en homomorfismen
  • Functoren
  • Functoren en datatypen
  • Catamorfismen en fusie
  • Generieke functies
  • Polytypische unificatie
2e gedeelte: In groepen aan generieke XML programmeerproblemen werken.
wijzigen?