Project Ideas
As noted in the syllabus, the coursework
will include a course project, which can be either individual or done in
groups of 2-3. The project might be developing a non-trivial application
in a constraint language, extending or even developing a new language, or
presenting and analyzing a set of papers from the literature.
Here are some project ideas. Of course, you are welcome to come up with
your own project instead. Please also feel free to ask about ideas you
think might work out!
Wallingford Extensions
Wallingford is an experimental constraint reactive programming language. A
very preliminary workshop paper is here;
the github repository is
at https://github.com/cdglabs/wallingford.
There are a variety of potential projects around extending it in different
directions (more on this at the first class session).
- Wallingford includes an integral macro that finds the integral
of the provided expression, either symbolically or numerically. (The
default behavior is to first try to find it symbolically, and if that is
too difficult, numerically.) The current symbolic integration
capabilities are very simple. For this project, extend them to handle a
wider class of expressions. An advantage of this project is that the
symbolic integration code is mostly independent of the rest of the
system, so that you could make progress without needing to delve
extensively into other parts of the code base. Depending on how much you
implement, this could be the entire project. Better, however, would be
to use this as a warmup project -- some simple additions would add a lot
of useful functionality -- and then move onto an additional project, for
example the numeric integration project described next. (In any case, my
recommendation is that symbolic integration as such isn't appropriate as
a research area -- it is heavily investigated and doing something novel
would require a lot of implementation work before getting to novel
aspects.)
- The current implementation of numeric integration is naive and also not
integrated with searching for the next time a when
or while condition becomes true. For this project, redo the
design and implementation. A good starting point is probably fourth
order Runge-Kutta, as is used in for example
Fran.
- The current Wallingford implementation has surprisingly good
performance for interactive graphical applications, considering that each
time the screen is refreshed there is a call out to the Z3 solver.
However, this seems unlikely to scale very well. For this project,
investigate compiling Wallingford. (There are already samples of
hand-compiled code for various demos, which could serve as examples of
what a compiler would output.) Emina says this is likely to be hard, and
doing it well seems more like a PhD-sized project rather than a course
project, but there are probably some really nice intermediate projects
that could be accomplished in a quarter. (So if you do this, be prepared
to adjust the goal depending on what you come up with along the
way.)
- A longer-term goal for Wallingford is to build a visual, end user
programming environment that makes this functionality more easily
available to end users (roughly, ThingLab plus reactivity). Design and
implement an initial version of this. Again, doing this well is more PhD
sized than course sized -- but in this case I'm confident there are some
nice intermediate projects that can be accomplished in a quarter.
- Work on formalizing the denotational and operational semantics for the
language. There is already some informal work on this, but it needs
considerable work by someone adept at the formal side of programming
languages.
- Develop a richer handling of simulation time vs. clock time. This
would include dropping frames in the viewer if the computation is taking
too long, and perhaps providing some guarantees about the relation
between simulation time and wall clock time into the semantics. In
addition, work on a semantics (and perhaps a prototype implementation)
that accommodates distribution and things with different clocks.
Other Ideas
- Investigate a reactive constraint replacement for HTML/Javascript.
The motivation for this project is that constraints seem like a good
mechanism to specify many desired properties of a web page in a way that
lets it be adapted to different output devices and user requirements and
preferences. There is already work in this direction, for example
an older research project on
Constraint
Cascading Style Sheets for the Web, and a recent deployment of this as
Grid Style Sheets. Integrate
this with reactive objects. For this project, I'd suggest building a few
compelling examples, just developing enough of the underlying language to
implement them. Concentrate on expressiveness, and ignore for now such
considerations as efficiency, compatibility, and security.
- Investigate how the paradigm of programming by demonstration could be
changed into programming by editing/manipulation/perturbation, and in
particular how this could be supported by constraints. The idea is that
you already have a program but want to modify it a little, rather than
obtaining a program from scratch. A sequence of such refinements could
gradually get you the program that you want. This workflow could better
fit the process of how we write programs. For example, a user might want
to edit the output of a data visualization (which is a program mapping a
data set to the visual domain) to indicate how this visualization should
change, e.g. by manipulating a point in a scatter plot to arrive at a
desired histogram. More interesting than tweaking visualizations is to
indirectly modify (by manipulating the output of the visualization) the
relational query that feeds into the visualization. This might be
implemented by solving a multi-way constraint that relates the input data,
relational query, and output. (Suggested by Ras Bodik.)
- There are lots of other ideas on this page:
http://www.decision-procedures.org/projects/.