Search

Most type systems that support polymorphic functions are based on a version of System-F. We argue that this limits useful programming paradigms for languages with lazy evaluation. We motivate an extension of System-F alleviating this limitation. First, using a sequence of examples, we show that for lazily evaluated languages current type systems may force one to write a program in an unnatural way; we in particular argue that in such languages the relationship between polymorphic and existential types can be made more systematic by allowing to pass back (part of) an existential result of a function call as an argument to the the function call that produced that value. After presenting our extension to System-F we show how we can implement the strict-state thread monad $\mathrm{ST}$ by using a returned existential type in specialising the polymorphic function which returns that type. Currently this monad is built-in into the runtime system of GHC and as such has become part of the language. Our proposed language extension, i.e. the introduction of polymorphic contexts, reverses the relationship between the context of a function call and the called function with respect to where it is decided with which type to instantiate a type variable.

Compilers, amongst other programs, often work with data that (slowly) changes over time. When the changes between subsequent runs of the compiler are small, one would hope the compiler to incrementally update its results, resulting in much lower running times. However, the manual construction of an incremental compiler is very hard and error prone and therefore usually not an option. Attribute grammars provide an attractive way of constructing compilers, as they are compositional in nature and allow for aspect oriented programming. In this work we extend previous work on the automatic generation of incremental attribute grammar evaluators, with the purpose of (semi-)automatically generating an incremental compiler from the regular attribute grammar definition, by adding support for incremental evaluation of higher order attributes, a well known extension to the classical attribute grammars that is used in many ways in compiler construction, for example to model different compiler phases.

Attribute Grammars (AGs) extend Context-Free Grammars with attributes: information gathered on the syntax tree that adds semantics to the syntax. AGs are very well suited for describing static analyses, code-generation and other phases incorporated in a compiler. AGs are divided into classes based on the nature of the dependencies between the attributes. In this paper we examine the class of Linearly Ordered Attribute Grammars (LOAGs), for which strict, bounded size evaluators can be generated. Deciding whether an Attribute Grammar is linearly ordered is an NP-hard problem. The Ordered Attribute Grammars form a subclass of LOAG for which membership is tested in polynomial time by Kastens' algorithm (1980). On top of this algorithm we apply an augmenting dependency selection algorithm, allowing it to determine membership for the class LOAG. Although the worst-case complexity of our algorithm is exponential, the algorithm turns out to be efficient for practical full-sized AGs. As a result, we can compile the main AG of the Utrecht Haskell Compiler without the manual addition of augmenting dependencies. The reader is provided with insight in the difficulty of deciding whether an AG is linearly ordered, what optimistic choice is made by Kastens' algorithm and how augmenting dependencies can resolve these difficulties.

Atze Dijkstra investigated whether road safety can be improved by making changes in road structure and road categorization according to the functional requirements of Sustainable Safety. One of these demands is that the fastest route is also the safest route. This is often not the case in practice. The results of this research will make it possible to check in the planning and design phases of a road network to which extent it will meet the Sustainable Safety requirements. Several (new) types of research methods and safety indicators were used to answer these questions. The road network has been analysed using the so-called (adapted) Integrated Network Design method. The safety aspects of routes have been determined using three safety indicators: a route score which describes the safety of a route (DV score), the number of conflicts that has been calculated in a microsimulation model (calculated conflicts), and the number of registered crashes. The number of calculated conflicts has a quantitative relation with the number of crashes, and the number of conflicts has a quantitative relation with the route score. Indirectly, through the number of conflicts, there is a relation between the DV score and the number of crashes. The DV score is therefore relevant for road safety research. In a study area, several routes with the same origin-destination relation have been investigated. The comparison of their DV scores shows that, among other things, the fastest route and the most chosen route do not always have the best scores. The safety of the routes that were travelled has afterwards also been calculated using crash rates. This indicates that the fastest routes are significantly less safe than the safest routes. These results are dependent on the given network in the study area. Adaptation of the network can change the results. The present study shows that presently the safest route often fails to be also the fastest route. Because drivers usually choose the fastest route, the author recommends developing policy to ensure that the fastest route is also the safest route.