Generic programming

Website:website containing additional information
Course code:INFOGP
Credits:7.5 ECTS (=5.25 old credit points)
Period:periode 3 (week 6 t/m 16, dwz 2-2-2004 t/m 16-4-2004; herkansing week 21)
Participants:up till now 15 subscriptions
Schedule:Dit is een oud rooster!
formgrouptimeweekroomteacher
college   ma 10-126-8,10-15 BBL-426 Johan Jeuring
  
wo 11-136-8,10-15 BBL-426
Contents:Software usually works with structured information; think of Web-browsers and HTML-documents. This structure can be represented by a data type or a DTD (Document Type Definition). If such a type changes, all programs that work on that type have to be changed too, although often the central problem does not change.

In the course on generic programming we will discuss methods with which problems can be formulated and solved for arbitrary data types or DTDs. The result is a generic program. An example of a generic program is a program for pattern matching: finding occurrences of a patterns in a given value. This problem is well known in the domain of strings, but it is equally important for trees or matrices. By specialising to a given type we get a normal, type-specific program. Many design patterns are also instances of generic programs.

In the course we will discuss generic programming by means of a number of example problems. You will also see some very basic category theory, which can be used to reason about generic programs. We will use the programming language Generic Haskell, an extension of Haskell that supports generic programming, in particular on XML related problems.

Literature:The literature exists of a number of articles that will be distributed during the course.
Course form:Lectures, exercises and/or practicals that have to be handed in, student presentations.
Exam form:A student will be graded by means of his or her presentation, and/or the exercises/practicals that will have to be handed in.
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:We will discuss the following topics.
  • sorting morphisms
  • XML,DTD,Schema
  • HaXml
  • Simply typed and polymorphic lambda calculus
  • Type-indexed values
  • Kind-indexed types
  • Generic programming for XML tools
  • Specialization
  • Proofs and derivations
wijzigen?