Advising

Lambda Reading Group: We’re a group of programming languages students and faculty that meets to discuss a different paper each week. If you’re interested in programming languages, you’re welcome to join! Just send me an email.

Current weekly meeting time (Fall 2018): Wednesday 11am, KEC 3057

Current Students

Graduated Students

Student Theses and Project Reports

  1. Imperative Programming with Variational Effects
    Alexander Grasley
    MS thesis, Oregon State University, 2018
    [Abstract, PDF]

    Variation is a commonly encountered element of modern software systems. Recent research into variation has led to increasing interest in the development of variational programming languages and corresponding variational models of execution. Variational imperative languages pose a particular challenge due to the complex interactions between side effects and variation. The development of interpreters for variational imperative languages has produced a number of techniques to address these interactions. This thesis builds upon and formalizes these techniques by defining a formal operational semantics for a simple imperative language that supports both variation and common side effects. We also provide an example of the successful implementation of these techniques in the form of the Resource DSL. One area in which variation is frequently encountered is in defining configurations and resource requirements for the deployment of modern software systems. To this end, we have developed the Resource DSL, a language that aids in the specification of resource requirements for highly configurable software systems.

  2. The Ownership Monad
    Michael G. McGirr
    MS project, Oregon State University, 2018
    [Abstract, PDF]

    The Rust programming language is a systems programming language with a strong static type system. A central feature of Rust’s type system is its unique concept of “ownership”, which enables Rust to give a user safe, low-level control over resources without the overhead of garbage collection. In Haskell, most data is immutable and many of the problems addressed by ownership in Rust simply don’t arise. However, ownership is still useful in Haskell in the context of mutable references and concurrency. This project report introduces the Ownership Monad, a monad that implements aspects of Rust’s ownership system as a library in Haskell. This will demonstrate many of the rules enforced by the ownership system in Rust in order to better understand the ownership-based method of tracking resources. This report will further explore the benefits such a system can provide for tracking resource use between concurrent threads.

  3. Formative Work Toward a Mixed-Initiative Programming Language
    Keeley Abbott
    MS thesis, Oregon State University, 2017
    [Abstract, PDF]

    Mixed-initiative programming entails collaboration between a computer system, and a human to achieve some desired goal or set of goals. Often these goals change or are amended in real time during the course of program execution. As such, the plans these programs are based on must adapt and evolve to accommodate this iterative process. This thesis collects a literature review of research done in the field of mixed-initiative programs that provides an understanding of the problems faced when attempting to integrate computer systems and human users, a previously published paper with formative work in understanding how humans write programs for other humans, and finally some initial work done to develop an embedded domain-specific language for mixed-initiative drone control.

  4. Principles of Variational Databases
    Parisa Ataei
    MS thesis, Oregon State University, 2017
    [Abstract, PDF]

    Data variations are prevalent in real-world applications. For example, software vendors have to handle numerous variations in the business requirements, conventions, and environmental settings of a software product. In database-backed software, the database of each version may have a different schema and content. As another example, data scientists often need to use a subset of the available databases because using non-relevant information may reduce the effectiveness of the results. Such variations give rise to numerous data variants in these applications. Users often would like to query and/or analyze all such variants simultaneously. For example, a software vendor would like to perform common tests over all versions of its product and a data scientist would like to find the subset of information over which the analytics algorithm delivers the most accurate results. Currently, there is not any systematic and principled approach to managing and querying data variations and users have to use their intuition to perform such analyses. We propose a novel abstraction called a variational database that provides a compact and structured representation of general forms of data variations for relational databases. As opposed to data integration approaches that provide a unified representation of all data sources, variational databases make variations explicit in both the schema definition and the query language without introducing too much complexity.

  5. Implementation Techniques for Variational Data Structures
    Meng Meng
    MS thesis, Oregon State University, 2017
    [Abstract, PDF]

    Many applications require not only representing variability in software and data, but also computing with it. To do so efficiently requires variational data structures that make variability explicit in the underlying data and the operations used to manipulate it. Variational data structures have been developed ad hoc for many applications, but there is little general understanding of how to design them or what tradeoffs exist among them.

    In this thesis, we introduce the concept of holes to represent variational data structures of different sizes and shapes. Moreover, we strive for a more systematic exploration and analysis of a variational data structure. We want to know how different design decisions affect the performance and scalability of a variational data structure, and what properties of the underlying data and operation sequences need to be considered.

    Specifically, we study several alternative designs of a variational stack and analyze how these design decisions affect the performance of a variational stack with different usage profiles. We evaluate variational stacks in a real-world scenario: in the interpreter VarexJ when executing real software containing variability. Finally, we discuss different ways of representing variational priority queues and show how this affects the performance of the variational Dijkstra’s algorithm.

  6. View-Based Editing of Variational Code
    Miles Van de Wetering
    Honors BS thesis, Oregon State University, 2017
    [Abstract, PDF]

    This paper discusses the merits of providing users variational views when editing variational code. I provide a plugin for the popular Atom Integrated Development Environment (IDE) which replaces #ifdef annotations commonly used by the C PreProcessor (CPP) with colored backgrounds, thus reducing code clutter and attempting to help programmers quickly distinguish code that belongs to different features. I also provide a number of helpful features designed to help the programmer create, remove, and refactor feature code. Finally, I present a user study conducted in order to determine how helpful each of the two main features (code folding and background color) are to programmers – it was determined that while there were no significant differences in efficiency or accuracy, the user experience was considerably enhanced.

  7. A Template CoprHD Storage Driver Based on the Southbound SDK
    Shujin Wu
    MS project, Oregon State University, 2017
    [Abstract, PDF]

    CoprHD is an open source software-defined storage and API platform which creates an abstraction layer over multi-vendor heterogeneous storage systems. It offers the ability to discover, pool and automate the management of the storage ecosystem with the help of storage drivers establishing connections between CoprHD and storage systems. On the demand of attracting more attentions from third-party storage companies, CoprHD community proposed a southbound driver SDK to simplify the process of developing a storage driver for CoprHD. ScaleIO storage driver, being the first one based on this southbound SDK, is implemented by us with Intel and EMC to serve the purposes to verify the southbound SDK and explore an effective way for the third-party driver development. This ScaleIO storage driver also acts as a template driver for the CoprHD community.

  8. A Formal Foundation for Variational Programming Using the Choice Calculus
    Spencer Hubbard
    MS thesis, Oregon State University, 2016
    [Abstract, PDF]

    In this thesis, we present semantic equivalence rules for an extension of the choice calculus and sound operations for an implementation of variational lists. The choice calculus is a calculus for describing variation and the formula choice calculus is an extension with formulas. We prove semantic equivalence rules for the formula choice calculus. Variational lists are functional data structures for representing and computing with variation in lists using the choice calculus. We prove map and bind operations are sound for an implementation of variational lists. These proofs are written and verified in the language of the Coq proof assistant.