Atze van der Ploeg

Computer science/Software enigineering researcher

Publications

  • Reflection without Remorse: Revealing a hidden sequence to speed up monadic reflection

    (Accepted,to appear)
    Authors: Atze van der Ploeg, Oleg Kiselyov
    Venue: Haskell Symposium 2014, Gotheburg, Sweden
    Abstract: A series of list appends or monadic binds for many monads performs algorithmically worse when left-associated. Continuation- passing style (CPS) is well-known to cure this severe dependence of performance on the association pattern. The advantage of CPS dwindles or disappears if we have to examine or modify the intermediate result of a series of appends or binds, before continuing the series. Such examination is frequently needed, for example, to control search in non-determinism monads. We present an alternative approach that is just as general as CPS but more robust: it makes series of binds and other such operations efficient regardless of the association pattern - and also provides efficient access to intermediate results. The key is to represent such a conceptual sequence as an efficient sequence data structure. Efficient sequence data structures from the literature are homogeneous and cannot be applied as they are in a type-safe way to series of monadic binds. We generalize them to type aligned sequences and show how to construct their (assuredly order-preserving) implementations. We demonstrate that our solution solves previously undocumented, severe performance problems in iteratees, LogicT transformers, free monads and extensible effects.
    PDF Bibtex
     
  • Monadic Functional Reactive Programming


    Authors: Atze van der Ploeg
    Venue: Haskell Symposium 2013, Boston, USA
    Abstract: Functional Reactive Programming (FRP) is a way to program reactive systems in functional style, eliminating many of the problems that arise from imperative techniques. In this paper, we present an alternative FRP formulation that is based on the notion of a reac- tive computation: a monadic computation which may require the occurrence of external events to continue. A signal computation is a reactive computation that may also emit values. In contrast to signals in other FRP formulations, signal computations can end, leading to a monadic interface for sequencing signal phases. This interface has several advantages: routing is implicit, sequencing signal phases is easier and more intuitive than when using the switching combinators found in other FRP approaches, and dynamic lists require much less boilerplate code. In other FRP approaches, either the entire FRP expression is re-evaluated on each external stimulus, or impure techniques are used to prevent redundant re-computations. We show how Monadic FRP can be implemented straightforwardly in a purely functional way while preventing redundant re-computations.
    PDF Bibtex
    Talk  
  • Drawing Non-layered Trees in Linear Time

    (Accepted,to appear)
    Authors: Atze van der Ploeg
    Venue: Software: Practice & Experience (journal)
    Abstract: The well-known Reingold-Tilford algorithm produces tidy layered draw- ings of trees: drawings where all nodes at the same depth are vertically aligned. However, when nodes have varying heights, layered drawing may use more vertical space than necessary. A non-layered drawing of a tree places children at a fixed distance from the parent, thereby giving a more vertically compact drawing. Moreover, non-layered drawings can also be used to draw trees where the vertical position of each node is given, by adding dummy nodes. In this paper we present the first linear time algorithm for producing non-layered drawings. Our algorithm is a modification of the Reingold-Tilford algorithm, but the original complexity proof of the Reingold-Tilford algorithm uses an invariant that does not hold for the non-layered case. We give an alternative proof of the algorithm and its extension to non-layered drawings. To improve drawings of trees of unbounded degree, extensions to the Reingold-Tilford algorithm have been proposed. These extensions also work in the non-layered case, but we show that they then cause a O(n^2) run-time. We then propose a modification to these extensions that restores the O(n) run-time.
    PDF Bibtex
     
  • A Library for Declarative Resolution-Independent 2D Graphics


    Authors: Paul Klint, Atze van der Ploeg (in alphabetical order)
    Venue: Symposium on Practical Aspects of Declarative Languages (PADL) '13
    Abstract: The design of most 2D graphics frameworks has been guided by what the computer can draw efficiently, instead of by how graphics can best be expressed and composed. As a result, such frameworks restrict expressivity by providing a limited set of shape primitives, a limited set of textures and only affine transformations. For example, non-affine transformations can only be added by invasive modification or complex tricks rather than by simple composition. More general frameworks exist, but they make it harder to describe and analyze shapes. We present a new declarative approach to resolution-independent 2D graphics that generalizes and simplifies the functionality of traditional frameworks, while preserving their efficiency. As a real-world example, we show the implementation of a form of focus+context lenses that gives better image quality and better performance than the state-of-the-art solution at a fraction of the code. Our approach can serve as a versatile foundation for the creation of advanced graphics and higher level frameworks.
    PDF Bibtex Talk
     
  • Towards a One-Stop-Shop for Analysis, Transformation and Visualization of Software


    Authors: Paul Klint, Bert Lisser, Atze van der Ploeg (in alphabetical order)
    Venue: International Conference on Software Language Engineering (SLE) '11
    Abstract: Over the last two years we have been developing the meta- programming language RASCAL that aims at providing a concise and effective language for performing meta-programming tasks such as the analysis and transformation of existing source code and models, and the implementation of domain-specific languages. However, meta-programming tasks also require seamlessly integrated visualization facilities. We are therefore now aiming at a One-Stop-Shop for analysis, trans- formation and visualization. In this paper we give a status report on this ongoing effort and sketch the requirements for an interactive visualization framework and describe the solutions we came up with. In brief, we propose a coordinate-free, compositional, visualization framework, with fully automatic placement, scaling and alignment. It also provides user interaction. The current framework can handle various kinds of charts, trees, and graphs and can be easily extended to more advanced layouts. This work can be seen as a study in domain engineering that will eventually enable us to create a domain-specific language for software visualization. We conclude with examples that emphasize the integration of analysis and visualization.
    PDF Bibtex