Oregon State University

Can’t find an event? We’re busy migrating to a new event calendar. Try looking at the new calendar



Event Details

MS Final Examination – Wyatt Allen

Monday, June 9, 2014 9:00 AM - 11:00 AM

Variational Parsing with the Choice Calculus
Commonly, a program is the product of a sequence of editing actions performed by a programmer with an editor or IDE. Although the final program is often what is of most interest, there are cases when one wants to get back to a previous version of the program by undoing some of the edits while keeping others. Thus, the result of editing a program is actually a set of related programs. This is the view of exploratory programming, and one of its goals is to provide programmers effective access to this set of programs. Currently, a programmer who wants to access a previous program variant has to tediously step backwards through a linear chain of character-based edits, often not knowing exactly when to stop or what edits should be kept or redone, or must laboriously navigate through coarse-grained commits in a version control system. As an alternative to this low-level and error-prone approach, programmers could be given more direct access to intermediate programs when they are represented as successfully parsed Abstract Syntax Tree (ASTs). Since most of these ASTs differ only a little, representing the set as one Variational Abstract Syntax Tree (VAST) has the advantage of better capturing and informing the programmer about commonalities and differences compared to storing a set of separate ASTs. A VAST could be produced by a parser that is able to process a variational token stream or string, which represent a program and its edits.

The goal of this project is to investigate the problem of variational parsing. Specifically, we will extend a monadic Haskell combinator library for defining top-down parsers by expanding parser combinators to work for variational token streams/strings and produce VASTs. We will explain the design of the extension and discuss challenges and problems encountered. We demonstrate the use of the library with two examples, by defining variational parsers for variational lambda calculus and for variational JavaScript. We also demonstrate how plain text edits can be systematically merged into a variational string.

Major Advisor: Martin Erwig
Committee: Alan Fern
Committee: Prasad Tadepalli 

Kelley Engineering Center (campus map)
Nicole Thompson
1 541 737 3617
Nicole.Thompson at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: