Here are some suggestions for projects. They mostly involve
improving the minigrace implementation in some useful way,
because that's where my current interests lie. You can also
make a proposal based on your own ideas.
- Better Graphics. As you know, Grace's
graphics capabilities are limited, in two ways. First,
they don't allow much in the way of graphical operations,
like scaling or rotation, even though these are supported by
the HTML5 Canvas that Grace uses to draw on. Second,
they are not very object-oriented, for example, they don't
allow one to compose graphical objects out of simpler
graphical objects; mouse clicks are not sent to the object
under the mouse, and so on. This project could focus
on designing a nice OO graphics interface, perhaps based on
the Morphic graphics system developed for Self and
Smalltalk, or it could focus on just enhancing the graphical
capabilities themselves. Performance may be a limiting
Last year a team of students created graphix, an
interface to the CreateJS
libraries, which provide much nicer garphics with a
simpler and more-oo inetrface. Unfrotunatley, it's not
quite complete, and there are issues with using it in a
separate window. Solving these problems would be a
very useful contribution; a working knowledge of HTML5
grahics is a prerequisite.
- A previous undergraduate project implemented a simple Omniscient
Debugger for Grace. (An omniscient
debugger lets one move backward as well as forward in
time; see the linked paper.) In addition to stepping,
it allows one to inspect variables. It runs (sort of)
in an older web IDE, but needs to be integrated into the
current programming environment, and made more
sophisticated. The goal is to support novice learning
rather than debugging "real world" programs; being able to see
objects react to requests is a powerful learning aid.
- Visual Test Runner. We have the gUnit
testing framework for Grace, and the dialect minitest
that supports simple inline tests for novices who have not
yet learned about inheritance.
To promote Test Driven Development I would like these to be
integrated into the Web IDE, so that a student can run a
test suite at the click of a button. It would be nice
to show the status of all modules loaded into the IDE (are
the tests are red or green?), and
to focus the IDE on a failing test. This would
make it easier to introduce testing early in an introductory
- Performance Monitor. Modern computers give us
the freedom to focus on clarity of expression in student
programs, rather than on minimizing execution
time. However, once students start processing
real-world data, execution time starts to
matter. For example, one of the assignments in
my introductory programming course was analyzing books for
authorship. This should be an O(n) task; some
carelessly-written programs made it O(n2),
and thus appeared to run forever! Of course, we
can explain the problem to the student, but a
performance monitor that will let the student see
this problem for themselves would promote more effective
learning. It would also help us in the next task.
- Performance Improvement. The current (self-hosting)
implementation of Grace is slow enough that students notice
that their programs take a long time to build.
While minigrace will probably never evolve into a
high-performance compiler, I believe that its current
performance could be improved by a factor of 10, by
optimizations already peformed by the V8 JIT. Doing so
would significantly improve the student experience,
and make it more likely that Grace be widely adopted.
- Efficient Dynamic Type-checking. Grace's
current dynamic type-checker is slow, because it repeatedly
re-checks the same object against the same type. There
is only a bounded number of different types of object in a
Grace program — it’s bounded by the number of object
constructors and classes) in the source. There
is also only a bounded number of type expressions.
Most type checks at a given place in the code are comparing
an object that was created by the same object constructor as
on the previous attempt! So, caching the results of
type checks is an obvious approach to speeding them up.
the minigrace runtime support library.
- Static type-checking. The static type-checker
is at present quite limited. The basic type-checking
algorithms work, I believe, but the software enginering to
integrate it with the module system and the standard prelude
remains to be done. Gradual typing remains to
be done, too.
- A Series of Dialects. Research in learning
has shown that it is beneficial for students to start
programming in a restricted language, and then shift to more
comprehensive languages as their skills develop.
Indeed, this is the motivation behind some of the
educational mini-languages like Logo and Scratch.
However, the problem with starting teaching in a
mini-language is that switching to a real language is
disruptive: students may see it as “starting over”, even
though the students are in fact building on a base of
acquired skills. Felleisen,
Findler, and colleagues solved this problem in DrScheme
(now DrRacket) by defining a series of increasingly powerful
languages, through which students can progress without
having to “unlearn” anything that they have already
mastered. Grace implements this idea with its dialect
A Grace dialect can extend the language by adding
new libraries, restrict access to the features of
the base language, and customize error messages to
the students' level of knowledge.
We have defined a few sample dialects, including a Logo-like
dialect, a dialect that enforces static types, and a
simple testing dialect, but we do not yet have a series of
dialects for teaching an introductory course.
This project might involve designing and implementing a
sequence of dialects that supports my personal teaching
preferences — so I would be your customer — or improving the
staticTypes dialect to make it more functional.
- A regular-expresson library for Grace. As
some students noted while working on the lexer, it would
sometimes be convenient to be able to use match(_)case(_)…
with regualr expressions. It's possible to define
patterns in Grace, so this could, at least in
principle, all be done as a library.
- Connecting to External Libraries. Students
interested in endangered species, melting glaciers, fish
harvests, indie music, art, earthquakes, or weather
patterns, all know that there is data “out there” on the
Internet. We would like them to be able to use Grace to
pull-down and analyze that data, which means providing more
Fortunately, this does not mean reproducing all of the
libraries available in other languages; all that we need do
is build a relatively simple converter that allows a Grace
program to access a “foreign” library. We have already
done this for some domains, such as accessing web pages,
drawing graphics and creating animations. I would like
to increase the versatility of Grace as a teaching tool by
creating more libraries; HTML audio is an obvious
candidate. In the long term, I would like a tool that
constructs the converters, given a description of the
interface of the foreign tool, and the desired interface of
the Grace library. Bulding a couple of
converters “by hand” would probably help the team figure out
exactly what it needs to do.
- JVM code generator. There are two code
generators for the minigrace compiler: one generates
JVM-code would be a better target: the JVM is universally
available, support concurrent processes, and, with the
advent of the invoke dynamic instruction, can support
dynamically-typed languages. This project would
involve emitting JVM byte codes from the existing abstract
syntax tree for Grace.
particular, it stores Grace methods in a methods
object attached to the JS representation of each Grace
object. This means that Grace method request has to
search through these methods objects in the receiver, and in
its superobject, and so on. I believe that it is
possible to devise a better representation for Grace objects
instead of explicit superobjects. This project would
who wants to learn about prototype-based inheritance.
The deliverables need not necessarily include a
full-function code generator, but instead a paper
design and a prototype generator that works on a few dozen
- Minigrace lexer. Extend the lexer that
you staretd writing in assignment 2 so that it lexes the
whole Grace language, and interfaces with the minigrace
parser. Interpolated strings may be the most complex
- Minigrace compiler cleanup. minigrace's
parser code generators are a bit of an embarrassment.
This project would involve applying the lessons of OO-design
that we have studied this quarter and creating better
structured code, and also eliminating some of the bugs that
we have seen during the quarter. The code
generators are rife with class tests, which could be removed
either by modularizing the code differently or by using the
visitor pattern consistently. The new code would need
to be integrated back into the minigrace source
pool. The goal here is to produce a better-structured
compiler that is no slower than the current one.
- Exytended collection Libraries for Grace. The
basic collection libraries include mutable sets and
dictionaries, and immutable sequences, but no efficient
immutable data structures using trees. We can
do better, perhaps by borrowing the interfaces from Google's
Guava libraries. Possible candidates are priority
queues, multisets and multi-dictionaries, bi-directional
dictionaries, and their immutable variants.
- Grace reflection interface. We do not have a
design or an implementation for Grace's reflection
interface. There is a module "mirrors" (should be
singular!) that alows one to ask about the names of the
methods defined on an object, and their arguments, and to
request one of these methods, but this is hardly
adequate. It should also be possible to ask what
fields are defined, which methods are confidential, what
annotations are present, what the source code looks like,
and so on. The information to answer these questions
is available, but there is no interface to access it.
This project would involve defining an interface to access
and (possibly) for C too.
- Enhance Grace's Web-based Programming Environment.
The ideal programming environment for Grace will be simple
to use, produce excellent error-messages, and will
capture all versions of the program for later analysis, so
that we can see if some miss-feature of the Grace language
or compiler is getting in the way of student success.
It should also support simple refactorings like renaming,
and show variable bindings graphically.
The current environment is simple, and the error messages
aren’t bad, but it lacks many of the above features.
has a simple core but which is far from simple in its
entirety. Useful enhancements include adding folders
to the client-side storage, and providing a way to re-upload
a new version of an existing file, as well as downloading
and re-uploading a zip archive containing all of the files
in the environment. It would also be nice to be able
to customize the ACE editor used for code editing, for
example, by adding buttons to insert characters like ⟦ and
Support for recursive compilation of imported modules would
be useful. At the command line, the compiler uses the
timestamps on source and object code files to decide if a
file needs to be recompiled; in the browser, there are no
timestamps on localstorage, so some other method
will be necessary.
Support for renaming (across a group of files) and
visualizing variable bindings would make a more significant
- Grace in your favorite programming environment.
Others have built good programming environments designed for
educational programming: Smalltalk, Dr Racket and
BlueJ are examples. I'm not sure whether Eclipse,
NetBeans, Visual Studio, etc qualify as being suitable for
novice users, but there is a clear argument in favour of
integrating Grace into an existing environment rather than
“starting over” building our own. This project would
probably be a feasibility study for a follow-on project that
would actually do the implementation, so I'm hesitant to
suggest it for this class, since a project for CS420/520
really needs a programming component.
- Grace Documentation Project. Many programming
langauges have dicsovered that documentation is most likely
to be kept up to date it it is included as comments in the
source code. But then there needs to be a tool that
extracts the docmentation for the source, and displays it in
a nice format, usually as a web page, sometimes also as
LaTeX source that can be compiled into a PDF document.
Java, Haskell, Python, Node, and even Nim have such
tools. Having documentation available in such a
form also makes it relatively simple to access form within
the programming environment, for example, in IDLE, a simple
Python environment, the documentation for a function is
displayed (after a short pause) when one types the open
parenthesis of a call.
Since it makes sense to reuse existing tools rather than
creating a new one, much of this project will be concerned
with setting conventions for documenting Grace, extracting
the documentation from the source, and translating it to the
right input format for some existing tool — essentially, a
parsing problem. It will also involve some background
research understanding the workflow for an existing tool,
and some work documenting the existing source of a few
sample modules. There is a graceDoc module, which
resulted from a previosu student project, but it needs
updating to deal with changes in Grace’s syntax.