Student Mentoring and Advising
Functional Programming Club
I am the faculty advisor for the OSU Functional Programming Club.
This is a student-run, official OSU club for students (graduate and undergraduate) who are interested in functional programming. The club meets weekly to learn, discuss, and explore functional programming together, and to hopefully build cool things in the process. All skill levels are welcome.
Here’s another link to the webpage, where you can find information on the mailing list, meeting times, current projects, and more!
Lambda Reading Group
I am founder and co-advisor (with Martin Erwig) of this informal group of students and faculty that meets weekly to discuss a different research paper on programming languages. Most of the participants are programming languages graduate students, but we are also regularly joined by students from the theory and software engineering groups, by advanced undergraduate students, and last summer, even by a local high school student.
If you’re interested in programming languages, you’re welcome to join too! Just send me an email so we know to expect you and so I can send you the paper to read in advance.
Current weekly meeting time (Spring 2020): Friday 1pm, Zoom
I am happy to lead a diverse team of smart, motivated, and kind students.
- Sebastian Benjamin, Honors thesis
- Margaret Walters, Honors thesis
Applying to Join Us
If you're interested in working with us, you should follow the standard process for applying to the EECS graduate program at OSU. However, please also send me an email!
Note that I get many generic inquiries during grad school application season, and I don't respond to most of these. If you are genuinely interested in working with my group, please clearly state why in your email (e.g. you are interested in some specific work we are doing, or I was recommended to you by someone). Consider that taking on a new student is a huge investment of time and energy and there are many applicants for a small number of positions, so you need to convince me that you are the one we should accept.
I say this not to scare you off from emailing me (if you're reading this, please do!) but to ensure that I notice your email in the deluge. :-)
Here is a list of my past students. You can find their theses and project reports below.
- Ghadeer Alkubaish, MS 2020 – currently on the job market!
- Qiaoran Li, MS 2019 – now at Google
- Alex Grasley, MS 2018 – now at Marketo
- Mike McGirr, MS 2018 – now at FP Complete
- Keeley Abbott, MS 2017 – now Operations Manager at OSU
- Meng Meng, MS 2017 – now at VMware
- Shujin Wu, MS 2017 – now at Google
- Spencer Hubbard, MS 2016 – now at Tableau
- Spencer Mitchell, RELU 2018–2019 – now an MS student at Dartmouth
- Miles Van de Wetering, Honors BS 2017 – now at Pariveda
Student Theses and Project Reports
- Integrating Side Effects in Variational Programs Using Algebraic EffectsMS thesis, Oregon State University, 2020
Variational programming supports efficiently executing many related programs at once by encoding all of the programs in one “variational program” that captures the differences among them statically and explicitly. An open problem in variational programming is how to handle side effects–if two program variants perform different side effects, we cannot separate the effect of one variant from the other since the outside world is not variational. A potential solution is to create variation-aware execution environments for variational programs, for example, a variational file system that keeps track of file variants corresponding to program variants. However, it is infeasible to do this for all kinds of effects. Also, there are different ways to handle the interaction of effects and variation that are incompatible with each other, preventing a one-size-fits-all solution. In this thesis, we argue that algebraic effects can be used to resolve the problem of combining variation and effects by enabling programmers to flexibly and incrementally extend a variational programming environment to handle new kinds of effects. We present a proof-of-concept prototype in the Eff programming language that demonstrates how a variational programming environment can be extended to support file input/output. Crucially, such extensions are done at the library level, which enables handling new kinds of effects and handling existing effects in multiple ways, both of which are essential in variational programming applications.
- Application of the Variational Database Management System to Schema Evolution and Software Product LinesMS project, Oregon State University, 2019
As a general solution to the problem of managing structural and content variability in relational databases, in previous work we have introduced the Variational Database Management System (VDBMS). VDBMS consists of a representation of a variational database (VDB) and a corresponding typed query language (v-query). However, since this is a novel database representation, there are no existing instances of VDBs or v-queries that can be used to evaluate the VDBMS. In this project, we present two case studies to demonstrate the use of VDBMS and support its evaluation. The case studies were constructed by systematically encoding variability scenarios from prior work and generating corresponding VDBs by adapting existing widely-used data sets. The first case study shows how to use the VDBMS to manage database variants under a schema evolution scenario. The second case study demonstrates how to integrate the VDBMS with a database-backed software product line. Each case study provides a VDB and a set of v-queries that will be used to evaluate the VDBMS. Additionally, we provide some insights into generating VDBs from relational databases that could assist future VDBMS users.
- Imperative Programming with Variational EffectsMS thesis, Oregon State University, 2018
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.
- The Ownership MonadMS project, Oregon State University, 2018
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.
- Formative Work Toward a Mixed-Initiative Programming LanguageMS thesis, Oregon State University, 2017
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.
- Principles of Variational DatabasesMS thesis, Oregon State University, 2017
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.
- Implementation Techniques for Variational Data StructuresMS thesis, Oregon State University, 2017
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.
- View-Based Editing of Variational CodeHonors BS thesis, Oregon State University, 2017
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.
- A Template CoprHD Storage Driver Based on the Southbound SDKMS project, Oregon State University, 2017
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.
- A Formal Foundation for Variational Programming Using the Choice CalculusMS thesis, Oregon State University, 2016
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.