• Home
• Publications
• Talks
• Software

Publications

[Show all abstracts]

[Hide all abstracts]

2011

• Armijn Hemel and Karl Trygve Kalleberg and Rob Vermaas and Eelco Dolstra. Finding Software License Violations Through Binary Code Clone Detection. In 8th Working Conference on Mining Software Repositories (MSR 2011), Honolulu, Hawaii, USA. May 2011. [pdf] [abstract]
  Abstract: Software released in binary form frequently uses third-party packages without respecting their licensing terms. For instance, many consumer devices have firmware containing the Linux kernel, without the suppliers following the requirements of the GNU General Public License. Such license violations are often accidental, e.g., when vendors receive binary code from their suppliers with no indication of its provenance. To help find such violations, we have developed the Binary Analysis Tool (BAT), a system for code clone detection in binaries. Given a binary, such as a firmware image, it attempts to detect cloning of code from repositories of packages in source and binary form. We evaluate and compare the effectiveness of three of BAT's clone detection techniques: scanning for string literals, detecting similarity through data compression, and detecting similarity by computing binary deltas.
• Sander van der Burg and Eelco Dolstra. A Self-Adaptive Deployment Framework for Service-Oriented Systems. In 6th International Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS 2011), Honolulu, Hawaii, USA. May 2011. [pdf] [abstract]
  Abstract: Deploying components of a service-oriented system in a network of machines is often a complex and labourious process. Usually the environment in which such systems are deployed is dynamic: any machine in the network may crash, network links may temporarily fail, and so on. Such events may render the system partially or completely unusable. If an event occurs, it is difficult and expensive to redeploy the system to the take the new circumstances into account. In this paper we present a self-adaptive deployment framework built on top of Disnix, a model-driven distributed deployment tool for service-oriented systems. This framework dynamically discovers machines in the network and generates a mapping of components to machines based on non-functional properties. Disnix is then invoked to automatically, reliably and efficiently redeploy the system.

2010

• Sander van der Burg and Eelco Dolstra. Automating System Tests Using Declarative Virtual Machines. In 21st IEEE International Symposium on Software Reliability Engineering (ISSRE 2010), San Jose, California, USA. November 2010. [pdf] [abstract]
  Abstract:

  Automated regression test suites are an essential software engineering practice: they provide developers with rapid feedback on the impact of changes to a system’s source code. The inclusion of a test case in an automated test suite requires that the system’s build process can automatically provide all the environmental dependencies of the test. These are external elements necessary for a test to succeed, such as shared libraries, running programs, and so on. For some tests (e.g., a compiler’s), these requirements are simple to meet.

  However, many kinds of tests, especially at the integration or system level, have complex dependencies that are hard to provide automatically, such as running database servers, administrative privileges, services on external machines or specific network topologies. As such dependencies make tests difficult to script, they are often only performed manually, if at all. This particularly affects testing of distributed systems and system-level software.

  This paper shows how we can automatically instantiate the complex environments necessary for tests by creating (networks of) virtual machines on the fly from declarative specifications. Building on NixOS, a Linux distribution with a declarative configuration model, these specifications concisely model the required environmental dependencies. We also describe techniques that allow efficient instantiation of VMs. As a result, complex system tests become as easy to specify and execute as unit tests. We evaluate our approach using a number of representative problems, including automated regression testing of a Linux distribution.

• Sander van der Burg and Eelco Dolstra. Automated Deployment of a Heterogeneous Service-Oriented System. In 36th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA), Lille, France. September 2010. [pdf] [abstract]
  Abstract: Deployment of a service-oriented system in a network of machines is often complex and labourious. In many cases components implementing a service have to be built from source code for the right target platform, transferred to the right machines with the right capabilities and activated in the right order. Upgrading a running system is even more difficult as this may break the running system and cannot be performed atomically. Many approaches that deal with the complexity of a distributed deployment process only support certain types of components or specific environments, while general solutions lack certain desirable non-functional properties, such as atomic upgrading. This paper shows Disnix, a deployment tool which allows developers and administrators to reliably deploy, upgrade and roll back a service-oriented system consisting of various types of components in a heterogeneous environment from declarative specifications.
• Eelco Dolstra and Andres Löh and Nicolas Pierron. NixOS: A Purely Functional Linux Distribution. In volume 20, number 5–6 of Journal of Functional Programming, pages 577–615. Cambridge University Press, 2010. [pdf] [doi] [abstract]
  Abstract: Existing package and system configuration management tools suffer from an imperative model, where system administration actions such as package upgrades or changes to system configuration files are stateful: they destructively update the state of the system. This leads to many problems, such as the inability to roll back changes easily, to deploy multiple versions of a package side-by-side, to reproduce a configuration deterministically on another machine, or to reliably upgrade a system. In this article we show that we can overcome these problems by moving to a purely functional system configuration model. This means that all static parts of a system (such as software packages, configuration files and system startup scripts) are built by pure functions and are immutable, stored in a way analogous to a heap in a purely functional language. We have implemented this model in NixOS, a non-trivial Linux distribution that uses the Nix package manager to build the entire system configuration from a modular, purely functional specification.
• Martin Bravenboer and Eelco Dolstra and Eelco Visser. Preventing Injection Attacks with Syntax Embeddings. In volume 75, number 7 of Science of Computer Programming, pages 473–495. Elsevier, July 2010. [doi] [pdf] [abstract]
  Abstract: Software written in one language often needs to construct sentences in another language, such as SQL queries, XML output, or shell command invocations. This is almost always done using unhygienic string manipulation, the concatenation of constants and client-supplied strings. A client can then supply specially crafted input that causes the constructed sentence to be interpreted in an unintended way, leading to an injection attack. We describe a more natural style of programming that yields code that is impervious to injections by construction. Our approach embeds the grammars of the guest languages (e.g. SQL) into that of the host language (e.g. Java) and automatically generates code that maps the embedded language to constructs in the host language that reconstruct the embedded sentences, adding escaping functions where appropriate. This approach is generic, meaning that it can be applied with relative ease to any combination of context-free host and guest languages.

2009

• Sander van der Burg and Eelco Dolstra and Merijn de Jonge and Eelco Visser. Software Deployment in a Dynamic Cloud — From Device to Service Orientation in a Hospital Environment. In ICSE 2009 Workshop on Software Engineering Challenges in Cloud Computing, pages 61–66, Vancouver, British Columbia, Canada. May 2009. [pdf] [acm] [abstract]
  Abstract: Hospital environments are currently primarily device-oriented: software services are installed, often manually, on specific devices. For instance, an application to view MRI scans may only be available on a limited number of workstations. The medical world is changing to a service-oriented environment, which means that every software service should be available on every device. However, these devices have widely varying capabilities, ranging from powerful workstations to PDAs, and high-bandwidth local machines to low-bandwidth remote machines. To support running applications in such an environment, we need to treat the hospital machines as a cloud, where components of the application are automatically deployed to machines in the cloud with the required capabilities and connectivity. In this paper, we suggest an architecture for applications in such a cloud, in which components are reliably and automatically deployed on the basis of a declarative model of the application using the Nix package manager.

2008

• Sander van der Burg and Eelco Dolstra and Merijn de Jonge. Atomic Upgrading of Distributed Systems. In First ACM Workshop on Hot Topics in Software Upgrades (HotSWUp), Nashville, Tennessee, USA. October 2008. [pdf] [acm] [abstract]
  Abstract: Upgrading distributed systems is a complex process. It requires installing the right services on the right machines, configuring them correctly, and so on, which is error-prone and tedious. Moreover, since services in a distributed system depend on each other and are updated separately, upgrades typically are not atomic: there is a time window during which some but not all services are updated, and a new version of one service might temporarily talk to an old version of another service. Previously we implemented the Nix package management system, which allows atomic upgrades and rollbacks on single systems. In this paper we show an extension to Nix that enables the deployment of distributed systems on the basis of a declarative deployment model, and supports atomic upgrades of such systems.
• Eelco Dolstra and Andres Löh. NixOS: A Purely Functional Linux Distribution. In ICFP 2008: 13th ACM SIGPLAN International Conference on Functional Programming, pages 367–378, Victoria, British Columbia, Canada. September 2008. [pdf] [acm] [abstract]
  Abstract: Existing package and system configuration management tools suffer from an imperative model, where system administration actions such as upgrading packages or changes to system configuration files are stateful: they destructively update the state of the system. This leads to many problems, such as the inability to roll back changes easily, to run multiple versions of a package side-by-side, to reproduce a configuration deterministically on another machine, or to reliably upgrade a system. In this paper we show that we can overcome these problems by moving to a purely functional system configuration model. This means that all static parts of a system (such as software packages, configuration files and system startup scripts) are built by pure functions and are immutable, stored in a way analogously to a heap in a purely function language. We have implemented this model in NixOS, a non-trivial Linux distribution that uses the Nix package manager to build the entire system configuration from a purely functional specification.
• Eelco Dolstra and Jurriaan Hage and Bastiaan Heeren and Stefan Holdermans and Johan Jeuring and Andres Löh and Clara Löh and Arie Middelkoop and Alexey Rodriguez and John van Schie. Report on the Tenth ICFP Programming Contest. In ICFP 2008: 13th ACM SIGPLAN International Conference on Functional Programming, Victoria, British Columbia, Canada. September 2008. [pdf] [acm] [abstract]
  Abstract:

  The ICFP programming contest is a 72-hour contest, which attracts thousands of contestants from all over the world. In this report we describe what it takes to organise this contest, the main ideas behind the contest we organised, the task, how to solve it, how we created it, and how well the contestants did.

  This year’s task was to reverse engineer the DNA of a stranded alien life form to enable it to survive on our planet. The alien’s DNA had to be modified by means of a prefix that modified its meaning so that the alien’s phenotype would approximate a given “ideal” outcome, increasing its probability of survival. About 357 teams from 39 countries solved at least part of the contest. The language of choice for discriminating hackers turned out to be C++.

• Eelco Dolstra and Eelco Visser. The Nix Build Farm: A Declarative Approach to Continuous Integration. In International Workshop on Advanced Software Development Tools and Techniques (WASDeTT 2008), Paphos, Cyprus. July 2008. [pdf] [abstract]
  Abstract: There are many tools to support continuous integration (the process of automatically and continuously building a project from a version management repository). However, they do not have good support for variability in the build environment: dependencies such as compilers, libraries or testing tools must typically be installed manually on all machines on which automated builds are performed. The Nix package manager solves this problem: it has a purely functional language for describing package build actions and their dependencies, allowing the build environment for projects to be produced automatically and deterministically. We have used Nix to build a continuous integration tool, the Nix build farm, that is in use to continuously build and release a large set of projects.
• Eelco Dolstra. Maximal Laziness — An Efficient Interpretation Technique for Purely Functional DSLs. In Eighth Workshop on Language Descriptions, Tools and Applications (LDTA 2008), volume 238, number 5 of Electronic Notes in Theoretical Computer Science, pages 81–99, Budapest, Hungary. Elsevier Science Publishers, April 2008. [pdf] [doi] [abstract]
  Abstract: In lazy functional languages, any variable is evaluated at most once. This paper proposes the notion of maximal laziness, in which syntactically equal terms are evaluated at most once: if two terms e₁ and e₂ arising during the evaluation of a program have the same abstract syntax representation, then only one will be evaluated, while the other will reuse the former’s evaluation result. Maximal laziness can be implemented easily in interpreters for purely functional languages based on term rewriting systems that have the property of maximal sharing — if two terms are equal, they have the same address. It makes it easier to write interpreters, as techniques such as closure updating, which would otherwise be required for efficiency, are not needed. Instead, a straight-forward translation of call-by-name semantic rules yields a call-by-need interpreter, reducing the gap between the language specification and its implementation. Moreover, maximal laziness obviates the need for optimisations such as memoisation and let-floating.

2007

• Eelco Dolstra and Jurriaan Hage and Bastiaan Heeren and Stefan Holdermans and Johan Jeuring and Andres Löh and Arie Middelkoop and Alexey Rodriguez and John van Schie and Clara Löh. Morph Endo! Report on the Tenth Interstellar Contest on Fuun Programming. Technical report UU-CS-2007-029, Faculty of Science, Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands. October 2007. (Distributed at ICFP 2007.) [pdf] [abstract]
  Abstract: The Tenth Annual ICFP Programming Contest was a 72-hour contest held July 20—23 2007 and organised in conjunction with the 12th ACM SIGPLAN International Conference on Functional Programming (ICFP 2007). As in the previous nine editions, the goal of the contest was to allow teams from all over the world to demonstrate the superiority of their favourite programming language. This year’s task was to reverse engineer the DNA of a stranded alien life form to enable it to survive on our planet. The alien’s DNA had to be modified by means of a prefix that modified its meaning so that the alien’s phenotype would approximate a given “ideal” outcome, increasing its probability of survival. In this report we describe the task, how to solve it, how we created it, and how the contestants fared. About 357 teams from 39 countries solved at least part of the contest. The language of choice for discriminating hackers turned out to be C++.
• Martin Bravenboer and Eelco Dolstra and Eelco Visser. Preventing Injection Attacks with Syntax Embeddings — A Host and Guest Language Independent Approach. In Sixth International Conference on Generative Programming and Component Engineering (GPCE'07), Salzburg, Austria. ACM Press, October 2007. [31% acceptance rate] [pdf] [acm] [abstract]
  Abstract: Software written in one language often needs to construct sentences in another language, such as SQL queries, XML output, or shell command invocations. This is almost always done using unhygienic string manipulation, the concatenation of constants and client-supplied strings. A client can then supply specially crafted input that causes the constructed sentence to be interpreted in an unintended way, leading to an injection attack. We describe a more natural style of programming that yields code that is impervious to injections by construction. Our approach embeds the grammars of the guest languages (e.g., SQL) into that of the host language (e.g., Java) and automatically generates code that maps the embedded language to constructs in the host language that reconstruct the embedded sentences, adding escaping functions where appropriate. This approach is generic, meaning that it can be applied with relative ease to any combination of host and guest languages.
• Eelco Dolstra and Armijn Hemel. Purely Functional System Configuration Management. In 11th Workshop on Hot Topics in Operating Systems (HotOS XI), pages 73–78, San Diego, California, USA. USENIX, May 2007. [20% acceptance rate] [pdf] [abstract]
  Abstract: System configuration management is difficult because systems evolve in an undisciplined way: packages are upgraded, configuration files are edited, and so on. The management of existing operating systems is strongly imperative in nature, since software packages and configuration data (e.g., /bin and /etc in Unix) can be seen as imperative data structures: they are updated in-place by system administration actions. In this paper we present an alternative approach to system configuration management: a purely functional method, analogous to languages like Haskell. In this approach, the static parts of a configuration — software packages, configuration files, control scripts — are built from pure functions, i.e., the results depend solely on the specified inputs of the function and are immutable. As a result, realising a system configuration becomes deterministic and reproducible. Upgrading to a new configuration is mostly atomic and doesn’t overwrite anything of the old configuration, thus enabling rollbacks. We have implemented the purely functional model in a small but realistic Linux-based operating system distribution called NixOS.
• Eelco Dolstra and Eelco Visser. Automated Software Testing and Release with Nix Build Farms. In Verification and Validation of Software Systems (VVSS-2007), Eindhoven, The Netherlands. March 2007.

2006

• Eelco Dolstra. The Purely Functional Software Deployment Model. PhD thesis, Faculty of Science, Utrecht, The Netherlands. January 2006. ISBN 90-393-4130-3. [pdf] [igitur] [abstract]
  Abstract: Software deployment is the set of activities related to getting software components to work on the machines of end users. It includes activities such as installation, upgrading, uninstallation, and so on. Many tools have been developed to support deployment, but they all have serious limitations with respect to correctness. For instance, the installation of a component can lead to the failure of previously installed components; a component might require other components that are not present; and it is generally difficult to undo deployment actions. The fundamental causes of these problems are a lack of isolation between components, the difficulty in identifying the dependencies between components, and incompatibilities between versions and variants of components.

  This thesis describes a better approach based on a purely functional deployment model, implemented in a deployment system called Nix. Components are stored in isolation from each other in a Nix store. Each component has a name that contains a cryptographic hash of all inputs that contributed to its build process, and the content of a component never changes after it has been built. Hence the model is purely functional.

  This storage scheme provides several important advantages. First, it ensures isolation between components: if two components differ in any way, they will be stored in different locations and will not overwrite each other. Second, it allows us to identify component dependencies. Undeclared build time dependencies are prevented due to the absence of “global” component directories used in other deployment systems. Runtime dependencies can be found by scanning for cryptographic hashes in the binary contents of components, a technique analogous to conservative garbage collection in programming language implementation. Since dependency information is complete, complete deployment can be performed by copying closures of components under the dependency relation.

  Developers and users are not confronted with components’ cryptographic hashes directly. Components are built automatically from Nix expressions, which describe how to build and compose arbitrary software components; hashes are computed as part of this process. Components are automatically made available to users through “user environments”, which are synthesised sets of activated components. User environments enable atomic upgrades and rollbacks, as well as different sets of activated components for different users.

  Nix expressions provide a source-based deployment model. However, source-based deployment can be transparently optimised into binary deployment by making pre-built binaries (keyed on their cryptographic hashes) available in a shared location such as a network server. This is referred to as transparent source/binary deployment.

  The purely functional deployment model has been validated by applying it to the deployment of more than 278 existing Unix packages. In addition, this thesis shows that the model can be applied naturally to the related activities of continuous integration using build farms, service deployment and build management.

2005

• Eelco Dolstra. Secure Sharing Between Untrusted Users in a Transparent Source/Binary Deployment Model. In 20th IEEE/ACM International Conference on Automated Software Engineering (ASE 2005), pages 154–163, Long Beach, California, USA. ACM Press, November 2005. [9% acceptance rate] [pdf] [acm] [abstract]
  Abstract: The Nix software deployment system is based on the paradigm of transparent source/binary deployment: distributors deploy descriptors that build components from source, while client machines can transparently optimise such source builds by downloading pre-built binaries from remote repositories. This model combines the simplicity and flexibility of source deployment with the efficiency of binary deployment. A desirable property is sharing of components: if multiple users install from the same source descriptors, ideally only one remotely built binary should be installed. The problem is that users must trust that remotely downloaded binaries were built from the sources they are claimed to have been built from, while users in general do not have a trust relation with each other or with the same remote repositories.

  This paper presents three models that enable sharing: the extensional model that requires that all users on a system have the same remote trust relations, the intensional model that does not have this requirement but may be suboptimal in terms of space use, and the mixed model that merges the best properties of both. The latter two models are achieved through a novel technique of hash rewriting in content-addressable component stores, and were implemented in the context of the Nix system.
• Eelco Dolstra and Martin Bravenboer and Eelco Visser. Service Configuration Management. In E. James Whitehead, Jr. and Annita Persson Dahlqvist (Eds.), 12th International Workshop on Software Configuration Management (SCM-12), pages 83–98, Long Beach, California, USA. September 2005. [pdf] [abstract]
  Abstract: The deployment of services — sets of running programs that provide some useful facility on a system or network — is typically implemented through a manual, time-consuming and error-prone process. For instance, system administrators must deploy the necessary software components, edit configuration files, start or stop processes, and so on. This is often done in an ad hoc style with no reproducibility, violating proper configuration management practices. In this paper we show that build management, software deployment and service deployment can be integrated into a single formalism. We do this in the context of the Nix software deployment system, and show that its advantages — co-existence of versions and variants, atomic upgrades and rollbacks, and component closure — extend naturally to service deployment. The approach also elegantly extends to distributed services. In addition, we show that the Nix expression language can simplify the implementation of crosscutting variation points in services.
• Eelco Dolstra. Efficient Upgrading in a Purely Functional Component Deployment Model. In George Heineman et al. (Ed.), Eighth International SIGSOFT Symposium on Component-based Software Engineering (CBSE 2005), volume 3489 of Lecture Notes in Computer Science, pages 219–234, St. Louis, Missouri, USA. Springer-Verlag, May 2005. © Springer-Verlag. [25% acceptance rate] [pdf] [abstract]
  Abstract: Safe and efficient deployment of software components is an important aspect of CBSE. The Nix deployment system enables side-by-side deployment of different versions and variants of components, complete installation, safe upgrades, and safe uninstalls through garbage collection. It accomplishes this through a purely functional deployment model, meaning that the file system content of a component only depends on the inputs used to build it, and never changes afterwards. An apparent downside to this model is that upgrading “fundamental” components used as build inputs by many other components becomes expensive, since all of these must be rebuilt and redeployed. In this paper we show that binary patching between sets of components enables efficient deployment of upgrades in the purely functional model, transparently to users. Sequences of patches can be combined automatically to enable upgrading between arbitrary versions. The approach was empirically validated.

2004

• Eelco Dolstra and Merijn de Jonge and Eelco Visser. Nix: A Safe and Policy-Free System for Software Deployment. In Lee Damon (Ed.), 18th Large Installation System Administration Conference (LISA '04), pages 79–92, Atlanta, Georgia, USA. USENIX, November 2004. [31% acceptance rate] [pdf] [abstract]
  Abstract: Existing systems for software deployment are neither safe nor sufficiently flexible. Primary safety issues are the inability to enforce reliable specification of component dependencies, and the lack of support for multiple versions or variants of a component. This renders deployment operations such as upgrading or deleting components dangerous and unpredictable. A deployment system must also be flexible (i.e., policy-free) enough to support both centralised and local package management, and to allow a variety of mechanisms for transferring components. In this paper we present Nix, a deployment system that addresses these issues through a simple technique of using cryptographic hashes to compute unique paths for component instances.
• Eelco Dolstra and Eelco Visser and Merijn de Jonge. Imposing a Memory Management Discipline on Software Deployment. In 26th International Conference on Software Engineering (ICSE 2004), pages 583–592, Edinburgh, Scotland. IEEE Computer Society, May 2004. [13% acceptance rate] [pdf] [acm] [abstract]
  Abstract: The deployment of software components frequently fails because dependencies on other components are not declared explicitly or are declared imprecisely. This results in an incomplete reproduction of the environment necessary for proper operation, or in interference between incompatible variants. In this paper we show that these deployment hazards are similar to pointer hazards in memory models of programming languages and can be countered by imposing a memory management discipline on software deployment. Based on this analysis we have developed a generic, platform and language independent, discipline for deployment that allows precise dependency verification; exact identification of component variants; computation of complete closures containing all components on which a component depends; maximal sharing of components between such closures; and concurrent installation of revisions and variants of components. We have implemented the approach in the Nix deployment system, and used it for the deployment of a large number of existing Linux packages. We compare its effectiveness to other deployment systems.
• Eelco Dolstra and Gert Florijn and Merijn de Jonge and Eelco Visser. Transparantie in variabiliteit: Heldere keuzes in een eenduidige configuratieomgeving. In volume 46, number 1 of Informatie, pages 18–21. February 2004. [pdf]

2003

• Eelco Dolstra and Gert Florijn and Merijn de Jonge and Eelco Visser. Capturing Timeline Variability with Transparent Configuration Environments. In International Workshop on Software Variability Management, Portland, Oregon, USA. May 2003. [pdf] [abstract]
  Abstract: Virtually every non-trivial software system exhibits variability: the property that the set of features—characteristics of the system that are relevant to some stakeholder—can be changed at certain points in the system’s deployment life-cycle. Some features can be bound only at specific moments in the life-cycle, while some can be bound at several distinct moments (timeline variability). This leads to inconsistent configuration interfaces; variability decisions are generally made through different interfaces depending on the moment in the life-cycle. In this paper we propose to formalize variability into a feature model that takes timeline issues into account and to derive from such feature models configuration interfaces that abstract over the life-cycle.
• Eelco Dolstra. Integrating Software Construction and Software Deployment. In Bernhard Westfechtel and André van der Hoek (Eds.), 11th International Workshop on Software Configuration Management (SCM-11), volume 2649 of Lecture Notes in Computer Science, pages 102–117, Portland, Oregon, USA. May 2003. [pdf] [abstract]
  Abstract: Classically, software deployment is a process consisting of building the software, packaging it for distribution, and installing it at the target site. This approach has two problems. First, a package must be annotated with dependency information and other meta-data. This to some extent overlaps with component dependencies used in the build process. Second, the same source system can often be built into an often very large number of variants. The distributor must decide which element(s) of the variant space will be packaged, reducing the flexibility for the receiver of the package. In this paper we show how building and deployment can be integrated into a single formalism. We describe a build manager called Maak that can handle deployment through a sufficiently general module system. Through the sharing of generated files, a source distribution transparently turns into a binary distribution, removing the dichotomy between these two modes of deployment. In addition, the creation and deployment of variants becomes easy through the use of a simple functional language as the build formalism.
• Eelco Dolstra and Gert Florijn and Eelco Visser. Timeline Variability: The Variability of Binding Time of Variation Points. In Jilles van Gurp and Jan Bosch (Eds.), Workshop on Software Variability Management, Groningen, The Netherlands. February 2003. [pdf]

2002

• Eelco Dolstra and Eelco Visser. Building interpreters with rewriting strategies. In Mark van den Brand and Ralf Lämmel (Eds.), Workshop on Language Descriptions, Tools and Applications (LDTA'02), volume 65, number 3 of Electronic Notes in Theoretical Computer Science, Grenoble, France. Elsevier Science Publishers, April 2002. [pdf] [abstract]
  Abstract: Programming language semantics based on pure rewrite rules suffers from the gap between the rewriting strategy implemented in rewriting engines and the intended evaluation strategy. This paper shows how programmable rewriting strategies can be used to implement interpreters for programming languages based on rewrite rules. The advantage of this approach is that reduction rules are first class entities that can be reused in different strategies, even in other kinds of program transformations such as optimizers. The approach is illustrated with several interpreters for the lambda calculus based on implicit and explicit (parallel) substitution, different strategies including normalization, eager evaluation, lazy evaluation, and lazy evaluation with updates. An extension with pattern matching and choice shows that such interpreters can easily be extended.

2001

• Eelco Dolstra and Eelco Visser. First-class rules and generic traversal. Technical report UU-CS-2001-38, Institute of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands. November 2001. [pdf] [abstract]
  Abstract: In this paper we present a functional language supporting first-class rules and generic traversal. This is achieved by generalizing the pattern matching constructs of standard functional languages. The case construct that ties rules together and prevents their reuse, is replaced by separate, first-class, pattern matching rules and a choice combinator that deals with pattern match failure. Generic traversal is achieved through application pattern matching in which a constructor application is generically divided into a prefix and a suffix, thus giving generic access to the subterms of a constructor term. Many highly generic term traversals can be defined in a type-safe way using this feature.

  These features support a direct and natural encoding of program transformation rules and strategies. The generalization of pattern matching subsumes several proposals for extensions of pattern matching such as views, guarded patterns, and transformational patterns.
• Eelco Dolstra. First Class Rules and Generic Traversals for Program Transformation Languages. Master’s thesis, INF/SCR-2001-15, Institute of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands. August 2001. [pdf] [abstract]
  Abstract: The subject of this thesis is the construction of programming languages suitable for the implementation of program transformation systems. First class rules and generic traversals are especially useful in such languages. Stratego, a language specifically intended for program transformations, supports these features, but is untyped and impure.

  In this thesis we develop a pure non-strict functional language called RhoStratego, incorporating features from Stratego. First class rules are obtained through the equivalent of Stratego’s left-biased choice operator. This approach is not only useful to strategic programming, but is also more powerful than existing proposals to extend pattern matching, such as views and pattern guards. Stratego’s generic traversal primitives are implemented through a more fundamental mechanism, the application pattern match, whereby constructed values can be deconstructed in a generic and typeable fashion. We present the syntax and semantics of the language, as well as the semantics of a strict variant.

  Furthermore, we have developed a type system for RhoStratego, which consists of the Hindley-Milner type system extended with rank-2 polymorphism and typing rules to support generic traversals. The type system is powerful enough to allow, and ensure the safety of, type unifying and type preserving generic transformations. We have implemented a type checker that infers all types, except rank-2 types for which annotations must be given.

  We also discuss the results of the implementation of a compiler for RhoStratego, and in particular how generic traversals and the choice operator can be implemented.
• Eelco Dolstra. Functional Stratego. In Eelco Visser (Ed.), Second Stratego Users Day, Utrecht, The Netherlands. February 2001. [ps.gz] [abstract]
  Abstract: Stratego is a domain-specific language intended for the construction of program transformation systems. To that end, the language has a number of interesting features; notably, first class pattern matching and generic traversal mechanisms. The question arises whether and how such features can be implemented in functional programming languages and Haskell in particular. In a rewrite system it is essential that one can easily recover from pattern match failure, so that alternative rewrite rules can be tried. Typical functional languages do not support this very well since local pattern match failure leads to global divergence. This article shows how to solve this problem by adding a choice operator to a simple functional language. It seems that this approach is not only useful to strategic programming, but is also more powerful than previous proposals to extend Haskell’s pattern matching, such as views, patterns guards, and transformational patterns. Furthermore, we discuss how the generic programming techniques can be employed to implement generic traversals.